Graph Coloring — Definition, Formula & Examples

Graph coloring is the assignment of labels (called colors) to the vertices of a graph such that no two vertices connected by an edge receive the same color. The minimum number of colors needed is called the chromatic number of the graph.

A proper $k$ -coloring of a graph $G = (V, E)$ is a function $c: V \to \{1, 2, \ldots, k\}$ such that $c(u) \neq c(v)$ for every edge $\{u, v\} \in E$ . The chromatic number $\chi(G)$ is the smallest integer $k$ for which a proper $k$ -coloring exists.

Key Formula

\chi(G) = \min\{k \in \mathbb{Z}^+ : G \text{ has a proper } k\text{-coloring}\}

Where:

$\chi(G)$ = Chromatic number — the minimum number of colors needed
$k$ = Number of colors used in the coloring
$G$ = The graph being colored

How It Works

To color a graph, start by picking a vertex and assigning it color 1. Move to an adjacent vertex and assign the lowest-numbered color not already used by its neighbors. Repeat for each remaining vertex. A greedy approach like this always produces a valid coloring, but it does not always use the fewest possible colors — the result depends on the order in which you process the vertices. Finding the true chromatic number is NP-hard in general, so exact solutions rely on backtracking or other algorithmic techniques for large graphs.

Worked Example

Problem: Find the chromatic number of the cycle graph C₅ (a pentagon with vertices A, B, C, D, E connected in a cycle).

Step 1: Try 2 colors. Assign color 1 to A, color 2 to B, color 1 to C, color 2 to D. Now E is adjacent to both D (color 2) and A (color 1), so neither color works.

Step 2: Since 2 colors fail, try 3. Assign: A → 1, B → 2, C → 1, D → 2, E → 3. Check every edge: no two adjacent vertices share a color.

Step 3: A valid 3-coloring exists and we proved 2 colors are insufficient, so the chromatic number is 3.

\chi(C_5) = 3

Answer: The chromatic number of C₅ is 3.

Why It Matters

Graph coloring models real scheduling and assignment problems. For instance, assigning exam time slots so no student has two exams at the same time reduces directly to a coloring problem. It also underpins compiler register allocation, frequency assignment in wireless networks, and map coloring (the famous Four Color Theorem).

Common Mistakes

Mistake: Assuming the greedy coloring algorithm always produces the minimum number of colors.

Correction: Greedy coloring depends on vertex ordering and can use more than χ(G) colors. It gives a valid coloring, not necessarily an optimal one.