Graph coloring and chromatic number

Graph coloring

A graph coloring (vertex coloring) of a simple graph is an assignment of colors to its vertices so that no two adjacent vertices get the same color. A coloring that satisfies this rule is called proper.

Chromatic number

The chromatic number χ(G) is the smallest number of colors needed for a proper coloring of G. To show χ(G) = k, show that k colors suffice and that fewer than k colors cannot work.

Standard values

Also χ(G) ≤ Δ(G) + 1 (greedy coloring).

Example

Triangle K₃ with vertices a, b, c: all three are mutually adjacent, so they need 3 different colors, χ(K₃) = 3. The square C₄ (a–b–c–d–a): color a, c red and b, d blue, so χ(C₄) = 2.

Application: scheduling exams, where courses are vertices, an edge joins courses sharing a student, and colors are time slots.