Polynomial Coloring Applications
Keywords:
Color polynomial, George Birkhoff formula, chromatic number, order of graphAbstract
Appropriate coloring to the vertices of a given graph is to give color to each vertex so that two vertices connected by an edge will not have the same color. The smallest number of appropriate coloring called the chromatic number, and is often denoted by χ ( ).
The number of ways to color the vertices of a given graph in colors, given by placing in ), which is called the color polynomial of the graph and which maintains:
, Where is the graph without the edge , and is the graph obtained from the omitting of the edge and shrinking the two vertices that apply to it into one vertex. (due [10]).
In this paper, we will expand on the relationship between the color polynomial and the order of the graph, while giving explicit formulas to the color polynomial.