Chromatic Number

Description:

• The least number of colors needed for a coloring of a graph.
• Denoted by $\chi (G)$

Some coloring boundings:

• An even length closed cycle is 2-colorable
  • $\chi (C_{even})=2$
• An odd-length closed cycle requires 3 colors
  • $\chi (C_{odd})=3$
• A complete graph $K_n$ requires $n$ colors: $\chi (K_n)=n$
• All bipartite graph is 2-colorable:  $\chi (K_{(m,n)})=2$

---