Graph Coloring & Chromatic Number

Proper colorings, the chromatic number, and the Four Color Theorem.

The idea

Definition (Proper coloring and chromatic number).

A proper coloring of a graph $G$ assigns a color to each vertex so that no edge has both endpoints the same color. The chromatic number $\chi(G)$ is the fewest colors any proper coloring of $G$ uses.

To illustrate what the colors stand for, suppose a department must fit its exams into time slots, and two exams cannot share a slot if some student sits both. Draw a vertex for each exam and join two vertices whenever their exams conflict. A proper coloring with the slots as colors is exactly a valid schedule, and $\chi(G)$ is the fewest slots that suffice.

Because $\chi(G)$ is a minimum, pinning it down takes two arguments. Exhibiting a proper coloring that uses $k$ colors proves $\chi(G) \le k$. Proving $\chi(G) \ge k$ requires showing that fewer colors cannot work — most often, that $G$ contains $k$ vertices all joined to one another, which must receive $k$ different colors. When the two bounds meet at the same number, that number is $\chi(G)$.

Ways to work on it

• Walkthrough. Proper colorings, complete and bipartite graphs, and odd cycles.
• Practice. Chromatic number of a standard named graph.
• Hardest. Pin down a wheel's chromatic number, then the Four Color Theorem.

Not sure where to start? Take the ten-question placement test.