Graph Coloring: Crayons, Conflicts, and the Chromatic Number

Introduction

Imagine you are a teacher arranging seating for a school exam. Some students are friends and will copy off each other — those students cannot sit in adjacent seats. You want to label every seat with a desk color so that no two friends share the same color. The minimum number of colors you need is an intrinsic property of the friendship network — and computing it is exactly what Graph Coloring is about.

Graph coloring is one of the most visually intuitive yet mathematically deep topics in graph theory. It connects directly to scheduling, map-making, register allocation in compilers, and one of the most famous theorems in all of mathematics: the Four Color Theorem.

In this post we will build the theory from scratch — from the Golden Rule through the chromatic number, famous graph families, greedy coloring, and real-world applications.

The Golden Rule of Graph Coloring

Definition

A proper vertex coloring of a graph $G = (V, E)$ is an assignment of a color to every vertex such that:

$$\text{if } (u,v) \in E \text{, then } \text{color}(u) \neq \text{color}(v)$$

In words: no two adjacent vertices may share the same color.

This is the single rule that governs everything in graph coloring. The “colors” are just labels — mathematically they are elements of the set $\{1, 2, \ldots, k\}$.

A graph is $k$-colorable if there exists a proper coloring that uses at most $k$ colors.

Why Not Just Give Every Vertex a Different Color?

You always can — if your graph has $n$ vertices, you can trivially assign each one its own unique color and satisfy the Golden Rule. But that is not interesting or useful. The real question is: what is the minimum number of colors needed?

$k$-Colorability

The variable $k$ counts how many colors are in our palette.

1-Colorable: The Hermits

When can a single color suffice? If you assign every vertex the same color, then any edge $(u,v)$ would connect two identically colored vertices — a violation. So:

Theorem: A graph is $1$-colorable if and only if it has no edges (every vertex is isolated).

Five isolated vertices — no edges, no conflicts. Every vertex gets the same color. $\chi(G) = 1$.

2-Colorable: The Bipartite Callback

Two colors mean we split vertices into two groups where all edges cross between them. That is exactly the definition of a bipartite graph from Post 08!

Theorem: A graph is $2$-colorable if and only if it is bipartite.

Set $A$ (red) and Set $B$ (blue). Every edge connects red to blue — no two red vertices are adjacent, no two blue vertices are adjacent. This is a valid 2-coloring, and it is valid because the graph is bipartite.

Proof sketch:
- ($\Rightarrow$) If a 2-coloring exists, the two color classes form the bipartition.
- ($\Leftarrow$) If the graph is bipartite with partition $(A, B)$, color $A$ with color 1 and $B$ with color 2.

3-Colorable: The Triangle

Consider $K_3$ — the triangle. Every vertex is adjacent to every other vertex, so every pair of vertices needs a different color.

• $A$ (red) is adjacent to $B$ and $C$ — so $B$ and $C$ cannot be red.
• $B$ (blue) is adjacent to $C$ — so $C$ cannot be blue either.
• $C$ must be a third color: green.

$\chi(K_3) = 3$. No matter how you try, two colors always fail on a triangle because it contains an odd cycle of length 3.

The “More is Easy” Rule

Here is a simple but important logical observation:

Theorem: If a graph is $k$-colorable, then it is also $(k+n)$-colorable for any $n \geq 1$.

Proof: Take any valid $k$-coloring. Pick any single vertex $v$ and recolor it with a brand new color not used anywhere else. Since the new color appears nowhere among $v$’s neighbors, no conflict is created. The graph is now $(k+1)$-colorable. Repeat for more extra colors. $\square$

Example: The even cycle $C_4$ (a square) is 2-colorable. Give the graph a 2-coloring with red and blue, then swap one vertex’s red for yellow. You now have a valid 3-coloring of the same graph.

$C_4$ with alternating red–blue. Since $C_4$ is an even cycle (bipartite), the alternation closes perfectly — $\chi(C_4) = 2$.

The consequence: claiming a graph is $100$-colorable is trivial. We care about the minimum.

The Chromatic Number $\chi(G)$

Definition

The chromatic number $\chi(G)$ (pronounced “kai of G”) is the minimum number of colors needed for a proper coloring of $G$.

A graph with $\chi(G) = k$ is called a $k$-chromatic graph.

Finding $\chi(G)$ in general is computationally hard (NP-complete), but for structured graph families we can determine it exactly.

Key Lower Bound: Clique Number

A clique in a graph is a set of vertices that are all mutually adjacent (i.e., a complete subgraph). If $G$ contains a clique of size $r$ — written $\omega(G) = r$ — then every vertex in that clique needs its own color:

$$\chi(G) \geq \omega(G)$$

This is our best simple lower bound. For example, the triangle $K_3$ inside any graph forces $\chi \geq 3$.

Note: The inequality can be strict. There exist triangle-free graphs ($\omega = 2$) with arbitrarily large chromatic number. These are called Mycielski graphs — but that topic belongs to advanced graph theory.

Chromatic Numbers of Famous Graph Families

1. Empty Graph ($E_n$)

No edges at all. Every vertex is isolated.

$$\chi(E_n) = 1$$

2. Complete Graph ($K_n$)

Every vertex is adjacent to every other vertex. No two vertices can ever share a color.

$K_4$ with 4 vertices: each gets a unique color (red, blue, green, purple).

$$\chi(K_n) = n$$

$K_n$ is the worst-case graph for coloring: it requires the maximum possible number of colors for its size.

3. Cycle Graphs ($C_n$)

Vertices arranged in a ring, each adjacent to exactly two neighbors.

Even cycles ($C_{2m}$ — any cycle with an even number of vertices):

Even cycles are bipartite. Alternate two colors around the ring — the pattern closes perfectly because there is an even number of steps.

$$\chi(C_{2m}) = 2$$

Odd cycles ($C_{2m+1}$ — any cycle with an odd number of vertices):

Alternate two colors (say red–blue) around the ring. When you reach the last vertex, it is adjacent to vertex 1 (red) and vertex $2m$ (blue on even cycle). With an odd count, vertices 1 and the last vertex are both forced to be the same color — a conflict. A third color is needed for the last vertex.

$$\chi(C_{2m+1}) = 3$$

$C_5$ coloring: vertices 1 (red), 2 (blue), 3 (red), 4 (blue), 5 — forced to be green because 5 is adjacent to both 1 (red) and 4 (blue). $\chi(C_5) = 3$.

Summary:

This also gives a clean restatement of the bipartite characterization:

Theorem: A cycle graph $C_n$ is bipartite if and only if $n$ is even.

4. Bipartite Graphs (General)

Theorem: $G$ is bipartite $\iff$ $\chi(G) \leq 2$.

More precisely:
- $\chi(G) = 1$ if $G$ is bipartite and has no edges (the empty graph).
- $\chi(G) = 2$ if $G$ is bipartite and has at least one edge.

Star graphs $S_{n+1} = K_{1,n}$ fall here: the central hub is one color, all leaf vertices share another. $\chi(S_{n+1}) = 2$ for $n \geq 1$.

5. Wheel Graphs ($W_n$)

A wheel graph $W_n$ is constructed by taking a cycle $C_{n-1}$ and adding one hub vertex connected to every vertex on the outer ring.

$W_5$ = hub $H$ + outer $C_4$. The hub $H$ (green) is adjacent to all outer vertices. The outer ring is $C_4$ (even), colored red–blue–red–blue. The hub cannot share red or blue, so it gets green. Total: $\chi = 3$.

$W_6$ = hub $H$ + outer $C_5$. The outer ring is $C_5$ (odd), requiring 3 colors. The hub is adjacent to all 5 outer vertices — it is adjacent to all 3 colors used on the ring — so it needs a 4th color (purple). Total: $\chi = 4$.

General rule for wheel graphs:

$$\chi(W_n) = \begin{cases} 3 & \text{if } n-1 \text{ is even (outer ring is even cycle)} \\ 4 & \text{if } n-1 \text{ is odd (outer ring is odd cycle)} \end{cases}$$

The hub always needs exactly one more color than the outer cycle requires.

Greedy Coloring

Finding the optimal chromatic number is NP-complete in general, but a simple greedy algorithm gives a practical upper bound.

The Algorithm

Process vertices in some fixed order $v_1, v_2, \ldots, v_n$. For each vertex $v_i$:

1. Look at all neighbors of $v_i$ that have already been colored.
2. Assign to $v_i$ the smallest-numbered color not already used by any of its colored neighbors.

This is called the First-Fit or Sequential Greedy coloring.

Demonstration

Processing order: $A \to B \to C \to D \to E$

Result: 3 colors total. $\chi(G) = 3$ for this graph (verified by the triangle $A$–$B$–$C$).

Greedy Bound

Theorem: For any graph $G$ with maximum degree $\Delta(G)$:
$$\chi(G) \leq \Delta(G) + 1$$

Every vertex has at most $\Delta$ neighbors, so the greedy algorithm needs at most $\Delta + 1$ colors (it can always find an unused color from the first $\Delta + 1$).

Brooks’ Theorem (1941) tightens this to $\chi(G) \leq \Delta(G)$ for all connected graphs that are not complete graphs or odd cycles. So $\Delta + 1$ is tight only for $K_n$ and $C_{2m+1}$.

Order Matters

The greedy algorithm is order-dependent: a bad vertex ordering can use more colors than necessary.

Example: The bipartite graph $K_{3,3}$ has $\chi = 2$. If vertices are ordered perfectly (all of set $A$ first, then all of $B$), greedy uses 2 colors. But if ordered $a_1, b_1, a_2, b_2, a_3, b_3$ (alternating), greedy still uses 2 because $b_1$ only sees $a_1$ and picks color 2. However, on other graphs, adversarial orderings can force up to $\chi_{bad} = \Delta + 1$ colors even when $\chi = 2$. The greedy algorithm never under-estimates $\chi$, but it can over-estimate it.

The Four Color Theorem

Perhaps the most famous theorem in graph theory — and one of the first major theorems proved by computer:

Four Color Theorem (Appel & Haken, 1976): Every planar graph is 4-colorable. In other words, any map drawn on a flat surface can be colored with at most 4 colors so that no two adjacent regions share a color.

Translating Maps to Graphs

The map coloring problem is a graph coloring problem in disguise:
- Each region (state, country) becomes a vertex.
- Two vertices are connected by an edge if the corresponding regions share a border.

The resulting graph is always planar (can be drawn without edge crossings), and the Four Color Theorem guarantees $\chi \leq 4$ for all planar graphs.

Five regions arranged as a ring with one central region. The central region borders all five outer regions (each a different color). No two outer regions adjacent to each other in the ring can share the same color as their neighbor. Four colors suffice to color the entire map.

Historical Note

The Four Color Conjecture was posed in 1852 by Francis Guthrie while coloring a map of England. It resisted proof for 124 years. Appel and Haken’s 1976 proof was controversial because it relied on a computer to verify 1,936 reducible configurations — the first major theorem proved with computer assistance. The proof has since been verified and simplified, but the theorem remains a landmark in mathematics.

The number 3 is not always enough: The map of the United States, for instance, requires 4 colors — the states of Nevada, Arizona, Utah, Colorado, and New Mexico form a structure requiring 4.

Practice Problems

Problem 1: Determine the Chromatic Number

Question: A graph $G$ has 6 vertices with edges forming two triangles that share one common edge (AB). Vertices: $A, B, C, D$ where $A$–$B$–$C$–$A$ is one triangle and $A$–$B$–$D$–$A$ is another. What is $\chi(G)$?

Problem 2: Odd vs. Even Cycle

Question: Cycles $C_7$ and $C_{12}$ — which requires more colors? What is the chromatic number of each?

Problem 3: Greedy Coloring

Question: Apply greedy coloring to $K_4$ (the complete graph on 4 vertices $A, B, C, D$, all pairs connected) in order $A \to B \to C \to D$. How many colors does greedy use? Is it optimal?

Problem 4: Chromatic Number from Clique

Question: A graph $G$ has a clique of size 5 (i.e., $K_5$ as a subgraph). What can you conclude about $\chi(G)$?

Problem 5: Wheel Graph

Question: What is $\chi(W_8)$? ($W_8$ has 8 vertices: a hub and an outer ring of 7 vertices.)

Problem 6: Exam Scheduling

Question: A university has 5 courses: Math, CS, Physics, History, English. The following pairs of courses share students (and thus cannot be scheduled at the same time): Math–CS, Math–Physics, Math–English, CS–Physics, CS–History, Physics–History, History–English. What is the minimum number of exam time slots needed?

Summary Table

Key inequalities:

$$\omega(G) \leq \chi(G) \leq \Delta(G) + 1$$

The clique number is a lower bound; $\Delta + 1$ is an upper bound (greedy bound). Brooks’ Theorem tightens the upper bound to $\Delta$ for most graphs.

Real-World Applications

Exam and Meeting Scheduling

If vertices are events (exams, meetings) and edges connect events that share a participant, then a proper $k$-coloring assigns events to $k$ non-overlapping time slots with no participant double-booked. The chromatic number is the minimum number of slots needed.

Math and History can share slot 1 because no student takes both. CS and English share slot 2. Physics takes slot 3 alone. Three slots suffice for five exams — that is the chromatic number of the conflict graph.

Register Allocation in Compilers

When a compiler translates high-level code to machine code, it must assign program variables to CPU registers. Two variables that are “live” at the same time cannot share a register. Build an interference graph — vertices are variables, edges connect variables live simultaneously — and color it. The chromatic number is the minimum number of registers needed; extra variables must be “spilled” to slower memory.

Sudoku Puzzles

Every solved Sudoku grid is a graph coloring with $k = 9$. The 81 cells are vertices. Two cells are connected by an edge if they share a row, column, or $3 \times 3$ box. Solving Sudoku is finding a proper 9-coloring of this specific graph.

Map Coloring and the Four Color Theorem

Any political map on a flat surface (a planar graph) can be colored with at most 4 colors. This is a theoretical guarantee — in practice, most real maps require at most 4 and many need only 3.

Wireless Frequency Assignment

In a cellular network, adjacent cell towers (base stations) cannot broadcast on the same frequency or they will interfere. Model towers as vertices and interference relationships as edges — the chromatic number is the minimum number of distinct frequencies needed. Reducing $\chi$ directly reduces spectrum usage and cost.

Key Takeaways

1. A proper coloring assigns colors to vertices so that no two adjacent vertices share a color. The variable $k$ denotes the number of colors used.
2. A graph is $k$-colorable if a proper coloring exists with at most $k$ colors. If $k$-colorable, it is also $(k+n)$-colorable for any $n \geq 1$.
3. The chromatic number $\chi(G)$ is the minimum $k$ for which $G$ is $k$-colorable. Finding it exactly is NP-complete in general.
4. $1$-colorable: only the empty graph (no edges). $2$-colorable: exactly the bipartite graphs.
5. Even cycles ($C_{2m}$) have $\chi = 2$; odd cycles ($C_{2m+1}$) have $\chi = 3$. A cycle is bipartite iff it is even.
6. Complete graphs need the most colors: $\chi(K_n) = n$. Wheel graphs follow the outer cycle plus one: $\chi = 3$ (even outer ring) or $\chi = 4$ (odd outer ring).
7. The clique number gives a lower bound: $\chi(G) \geq \omega(G)$. Greedy coloring gives an upper bound: $\chi(G) \leq \Delta(G) + 1$.
8. Greedy coloring assigns the smallest available color to each vertex in sequence — fast and practical, but order-dependent and not always optimal.
9. The Four Color Theorem (1976): every planar graph has $\chi \leq 4$. Any flat map can be colored with 4 colors.
10. Graph coloring models real problems including exam scheduling, register allocation, frequency assignment, and map coloring.

Explore Further

Use the GraphArena Playground to experiment:

• Build the triangle $K_3$ and verify that 2-coloring always fails — try every possible 2-assignment.
• Build $C_5$ and $C_6$ side by side. Trace through the alternating 2-coloring on each: see exactly where $C_5$ forces a third color at the closing edge.
• Build $W_5$ (hub + $C_4$) and $W_6$ (hub + $C_5$). Color the outer ring first, then try to color the hub — observe that it needs one extra color.
• Try the greedy algorithm on $K_{3,3}$: order vertices $a_1, b_1, a_2, b_2, a_3, b_3$ and watch how greedy picks colors. Then reorder all $a$’s first and compare.
• Build a 5-clique ($K_5$) and confirm that $\chi = 5$ — every vertex needs its own color.
• Model the exam scheduling example: 5 courses, 7 conflict edges. Find a 3-coloring and verify no two conflicting courses share a slot.

The chromatic number sits at the intersection of algorithms, combinatorics, and applications — a single number that captures the essential “conflict structure” of any graph.