Chromatic Polynomial
Introduction: A given graph G of n vertices can be properly coloured in many different ways using a sufficiently large number of colours. This property of a graph is expressed elegantly by means of a polynomial. This polynomial is called the chromatic polynomial of G. The value of the chromatic polynomial Pn (λ) of a graph with n vertices gives the number of ways of properly colouring the graph, using λ of fewer colours. Let Ci be the different ways of properly colouring G using exactly i different colours. Since i colours can be chosen out of λ colours in 
different ways, there are ci different ways of properly colouring G using exactly i colours out of λ colours. Since i can be any positive integer from 1 to n (it is not possible to use more than n colours on n vertices), the chromatic polynomial is a sum of these terms, that is,
Each Ci has to be evaluated individually for the given graph.
For example, any graph with even one edge requires at least two colours for proper colouring, and therefore C1 = 0.
A graph with n vertices and using n different colours can be properly coloured in n ! ways. that is, Cn = n !.
Problem . Find the chromatic polynomial of the graph given in Figure (2.70).
Since the graph in Figure 2.70 has a triangle, it will require at least three different colours for proper colourings.
Therefore, C1 = C2 = 0 and C5 = 5 !
Moreover, to evaluate C3, suppose that we have three colours x, y and z.
These three colours can be assigned properly to vertices v1, v2 amd v3 in 3 ! = 6 different ways.
Having done that, we have no more choices left, because vertex v5 must have the same colour as v3 and v4 must have the same colour as v2.
Therefore, C3 = 6.
Similarly, with four colours, v1, v2 and v3 can be properly coloured in 4 • 6 = 24 different ways.
The fourth colour can be assigned to v4 or v5, thus providing two choices.
The fifth vertex provides no additional choice.
Therefore, C4 = 24 • 2 = 48.
Substituting these coefficients in P5(λ), we get, for the graph in Figure (2.70).
P5(λ) = λ(λ – 1)(λ – 2) 2λ(λ – 1)(λ – 2)(λ – 3) λ(λ – 1)(λ – 2)(λ – 3)(λ – 4) = λ(λ – 1)(λ – 2)(λ2 – 5λ 7)
The presence of factors λ – 1 and λ – 2 indicates that G is at least 3-chromatic.