Mathwords logoMathwords

Chromatic Number — Definition, Formula & Examples

The chromatic number of a graph is the smallest number of colors needed to color every vertex so that no two adjacent vertices share the same color.

For a graph G=(V,E)G = (V, E), the chromatic number χ(G)\chi(G) is the minimum positive integer kk such that there exists a proper kk-coloring of GG—that is, a function c:V→{1,2,…,k}c: V \to \{1, 2, \dots, k\} satisfying c(u)≠c(v)c(u) \neq c(v) for every edge {u,v}∈E\{u, v\} \in E.

Key Formula

ω(G)≤χ(G)≤Δ(G)+1\omega(G) \leq \chi(G) \leq \Delta(G) + 1
Where:
  • χ(G)\chi(G) = Chromatic number of graph G
  • ω(G)\omega(G) = Clique number — size of the largest complete subgraph of G
  • Δ(G)\Delta(G) = Maximum degree of any vertex in G

How It Works

To determine the chromatic number, you try to color the graph with as few colors as possible while ensuring no edge connects two same-colored vertices. Start by checking whether the graph is 1-colorable (only possible if it has no edges), then 2-colorable (bipartite), and so on. A useful lower bound is the clique number ω(G)\omega(G), since every vertex in a clique needs a distinct color. An upper bound is Δ(G)+1\Delta(G) + 1, where Δ(G)\Delta(G) is the maximum vertex degree (Brooks' theorem tightens this for most graphs). In general, finding χ(G)\chi(G) exactly is NP-hard, so for large graphs you often rely on bounds and heuristics.

Worked Example

Problem: Find the chromatic number of the cycle graph C5C_5 (a 5-vertex cycle).
Step 1: Label the vertices v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5 around the cycle. Try a 2-coloring: alternate colors red and blue. Assign red to v1v_1, blue to v2v_2, red to v3v_3, blue to v4v_4. When you reach v5v_5, it is adjacent to both v4v_4 (blue) and v1v_1 (red), so neither color works.
Step 2: Since 2 colors fail, try 3 colors. Assign red to v1v_1, blue to v2v_2, red to v3v_3, blue to v4v_4, and green to v5v_5. Now v5v_5 is adjacent to v4v_4 (blue) and v1v_1 (red), and green differs from both. Every edge connects vertices of different colors.
Step 3: We showed 2 colors are insufficient and 3 colors suffice.
χ(C5)=3\chi(C_5) = 3
Answer: The chromatic number of C5C_5 is 3.

Why It Matters

Chromatic numbers appear in scheduling problems—assigning exam time slots so no student has two exams at once maps directly to graph coloring. They also arise in compiler register allocation and frequency assignment in wireless networks.

Common Mistakes

Mistake: Assuming the chromatic number always equals the clique number.
Correction: The clique number ω(G)\omega(G) is only a lower bound. Many triangle-free graphs (where ω=2\omega = 2) still require 3 or more colors—C5C_5 is a classic example.