Polynomial Coloring Applications

Abstract

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.