Chromatic Polynomial

Chromatic Polynomial :

The chromatic polynomial C(G,λ)of graph G denotes the different number of
colorings which are possible for G with at most λ colors. For example in the following Graph(K3), no coloring is possible for λ<=2 colors. With λ=3, 6 colorings are possible
which is equal to factorial(3). Since first vertex can be colored in λ

ways, second vertex in λ-1 and third vertex in λ-2 ways, so total number of colorings
possible is λ(λ-1)( λ-2).
Arguing in the similar fashion, we can arrive at following chromatic polynomials :

(i) C(G, λ) = λⁿ for a null graph G with n vertices.


(ii) If G is an open path with n vertices :
C(G, λ) = λ .λ^n-1

(iii) If G is the complete graph K_n
C(G, λ) = λ(λ-1)( λ-2)….( λ-n+1)

(iv) If G_i, 1<=i<=k, are components of graph G,
then C(G, λ) = Π_i=1^k C(G_i, λ) = C(G₁, λ).C(G₂, λ)…C(G_k, λ)

Finding out chromatic number of a graph from its chromatic polynomial:
Remember what’s the chromatic number?
Minimum number of colors required in order to color a graph such that
none of its adjacent vertices are of same color.
Now, Chromatic number has to be an integer.
Also, Chromatic polynomial should always be >0.
So, the minimum value of λ for which the chromatic
polynomial is >0, is the chromatic number.
For e.g.,

for C(G, λ) = λ(λ-1)( λ-2)

the minimum positive integer value of λ for which the polynomial is >0
is 2. Which is indeed the chromatic number of K₃.

Decomposition Theorem for chromatic polynomials :
If we obtain two graphs G₁ and G₂ from G in the following way :

(i) Obtain G1 by removing an edge (v1,v2) from G.
(i) Obtain G2 by fusing/collapsing v1,v2 in G.

Then :

C(G₁, λ) = C(G, λ) + C(G₂, λ)

For e.g.

Let G be the following graph :

then if I remove the edge (a,b) and obtain G₁

chromatic polynomial for G₁ is λ² .
And if I fuse/collapse a and b to obtain G₂ :

chromatic polynomial for G₂ is λ.
In order to obtain C(G, λ),

C(G, λ) = C(G₁, λ) – C(G₂, λ)

= λ² – λ = λ(λ -1),

which is indeed correct.

Similarly you can obtain the chromatic polynomial for the following
graph :

By observing that if you fuse/collapse b,d you obtain K₃, whose
chromatic polynomial is known to you and if you remove the edge
(b,d) you obtain an open path with 4 vertices, whose chromatic
polynomial is also known to you.
You should get the following C.P. for the above graph :

C(G, λ) = λ(λ-1)( λ² - 3λ + 3)