Chromatic Number

Chromatic number of a graph is the minimum value of kk for which the graph is k-colorablek-colorable.

In other words, it is the minimum number of colors needed for a proper-coloring of the graph.

Chromatic number of a graph GG is denoted by χ(G)χ(G). And a graph with χ(G)=kχ(G)=k is called a k-k-chromatic graph.

You might have noticed in the previous chapter (on k-Colorable Graphs) that some of the problems involved chromatic coloring.

Now we take a look at some common types of graph and their chromatic numbers.

Empty Graph: It's a graph without any edges (|E|=0|E|=0). All the vertices are isolated. χ(G)=1χ(G)=1. Note that an empty graph is also bipartite.

Bipartite Graph: An empty bipartite graph has χ(G)=1χ(G)=1. A non-empty bipartite graph has χ(G)=2χ(G)=2. Using this, we arrive at the following result.

Theorem: A graph GG is bipartite if and only if χ(G)≤2χ(G)≤2.

This can be easily established by observing that any graph with χ(G)≤2χ(G)≤2 is 2-2-colorable, and hence bipartite. The converse, has already been established earlier.

Star Graph: A star graph of order n+1n+1, denoted by Sn+1Sn+1, is the complete bipartite graph K1,nK1,n, where n≥0n≥0. So, it has same chromatic number as a bipartite graph.

Cycle graph: A cycle graph of order nn is denoted by CnCn. A cycle of odd order has χ(C2n+1)=3χ(C2n+1)=3, and that of even order has χ(C2n)=2χ(C2n)=2. So, a cycle of even order is also bipartite.

Wheel graph: A wheel graph of order n+1n+1 is obtained from CnCn by connecting all its vertices to a new vertex (called hub). Wheel graph of order nn is denoted by WnWn. A wheel of odd order has χ(W2n+1)=4χ(W2n+1)=4, and that of even order has χ(W2n)=3χ(W2n)=3.

Complete Graph: Since each vertex is connected to every other vertex, we have χ(Kn)=nχ(Kn)=n.