Application of Chromatic Polynomial

We can find the chromatic number of a graph. Here is a graph G₁, let’s find its chromatic number.

The Graph G₁ has 5 vertices so the chromatic polynomial  f(G₁,λ) = c₁ ^λC₁ +  c₂  ^λC₂+  c₃ ^λC₃ + c₄  ^λC₄ + c₅  ^λC₅

But here G₁ can not be color with 1 color so we can say c₁ = 0

in the same way ,

 c2 = 0
c3 = 3! = 6
c4 = 4! x 2! = 48
c5  = 5! = 120

Explanation For Chromatic Polynomial

With 1 or 2 color we cant color this graph so c₁ and c₂ equals to 0 .

When we have 3 colors , for the first vertex P we have 3 options to choose, for T there are only 2 colors to choose as it is adjacent to vertex P , for S,R,Q we have only one color to color the vertex. so c₃ = 3 × 2 × 1 × 1 × 1 = 3!

same for c₄ and c₅ .

c₄ = 4 × 3 × 2 × 2 × 1 = 4! × 2 = 48

c₅ = 5 × 4 × 3 × 2 × 1 = 5! = 120 , here number of vertices and number of colors are same then so we can directly conclude that .

So the chromatic polynomial ,

f(G1,λ) = 6 λC3 + 48 λC4 + 120 λC5
            = 6×((λ(λ-1)(λ-2))/3!) + 48×((λ(λ-1)(λ-2)(λ-3))/4!) + 120×((λ(λ-1)(λ-2)(λ-3)(λ-4))/5!) 
            = λ(λ-1)(λ-2) + 2λ(λ-1)(λ-2)(λ-3) + λ(λ-1)(λ-2)(λ-3)(λ-4)

Here, we use the formula of combination above, ⁿC_k = n!/(k! × (n-k)! )

ⁿC_k = n(n-1)(n-2)….(n-k+1)(n-k)! / k! × (n-k)!

= n(n-1)(n-2)….(n-k+1)/k!

f(G1,1) = f(G1,2) = 0,
but f(G1,3) = 3(3-1)(3-2) = 3 x 2 x 1 = 6 ≠ 0 

So, Chromatic Number of the graph is 3.

Conclusion 

The chromatic polynomial is nothing but a counting technique. A graph can be colored with some colors in different ways, but here we should keep in mind one thing that adjacent vertices must have different colors. From the chromatic polynomial we will know the smallest number of colors required to color a graph properly which is also known as chromatic number of the graph.

The chromatic polynomial of graph G is a polynomial function which defines how many ways we can color a graph with some number of colors. So we can write chromatic polynomial of a graph of n vertices denoted by f(G,λ), where we have λ number of colors.

What is Complete Graph?

• It is a type of graph where every pair of vertices are connected by an unique edge.
• It ensures every node is directly connected to other nodes.
• If there are n vertices in any complete graph then number of edges = (n×(n-1)/2).
• Each vertex is connected to all other vertex, except itself so the degree of each vertex is n-1 in a complete graph.