What is Chromatic Polynomial?

1. It represents the number of ways we can color vertices of graph with given number of colors such that no adjacent vertices have same color.
2. It is a important tool in graph theory for studying coloring problems and has various application in fields like computer science.

Chromatic Polynomial for a Complete Graph

Here we take a complete graph with v number of vertices and we have  λ number of colors c₁ , c₂ , c₃ ….. cλ

So we can say  λ ≥ v.

In a complete graph all vertices are adjacent to each other, so each of them must be colored with different or distinct colors.

Now in the picture , for P vertex we have all the options available means P can be assigned with n number of colors. Similarly for Q, we can not use the same color which already used to color vertex P, so now we have ( λ-1) number of colors to assign. Same way vertex R can be assigned with ( λ-2) colors. When we reach at the last vertex continuing this way, the last vertex can be assigned with  λ-(v-1) = n-v+1 no of colors.

By using the concept of counting, k_v is colored in ( λ-1)( λ-2)( λ-3)….( λ-v+1) ways where  λ is number of colors.

Thus, f(k_v,  λ) =  λ( λ-1)( λ-2)( λ-3)….( λ-v+1)

Examples of Chromatic Polynomial

Let’s consider some examples for better understanding.

Example 1: Let G be a graph and there are λ number of colors like C₁,C₂,C_3,C₄….C_λ . Here P,Q,R are three vertices which are adjacent to each other, each of them assigned with distinct color.

Now, if P can be assigned with λ number of color then Q can be assigned with λ-1 number of colors. So the graph G will be colored in  λ(λ -1)(λ -2) ways.

Here we can say, f(G,λ) =  λ(λ -1)(λ -2) =  λ³ – 3λ² + 2λ.

We can understand it with a simple example, if we have 10 colors and we are supposed to color a graph having three vertices, then the graph may be colored in 10 x 9 x 8 = 720 ways.

Example 2:

It is a complete graph with 4 vertices ( graph G₂ ).

the graph will be colored in λ(λ -1)(λ -2)( λ-3) ways so that, f( G₂ ,λ) = λ(λ -1)(λ -2)( λ-3).

Example 3:

• The chromatic polynomial of a complete graph with 5 vertices

f(k₅, λ) =  λ( λ-1)( λ-2)( λ-3)( λ-4)

• The chromatic polynomial of a complete graph with 7 vertices

f(k₇, λ) =  λ( λ-1)( λ-2)( λ-3)( λ-4)( λ-5)( λ-6)

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.