Chromatic Polynomial

1. What is Chromatic Number of a Graph?

The minimum number of colors such that adjacent vertices of the graph should not have same color is chromatic number of the graph.

2. How to find Chromatic Number from Chromatic Polynomial ?

The chromatic number is nothing but the smallest value of λ such that f(G,λ) ≠ 0. We can denote chromatic number as χ(G).

3. Can we use Chromatic Polynomial to determine if a Graph is Planar?

We can not determine if the graph is planer or not by using only chromatic polynomial.

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.