10.4 Graph Coloring, Chromatic Number Bounds & the Four Color Theorem

Back to Discrete Mathematics Notes

📚Module 10: Advanced Graph Theory: Trees, Planarity & ColoringTopic 10.4: Coloring & Chromatic Numbers⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Political Maps & University Exam Scheduling

Think of coloring as conflict-free resource scheduling:

1. The Map Coloring Rule: You are a cartographer coloring a world map. Countries that share a common land border cannot be painted the same color (otherwise, you cannot tell where one country ends and the next begins). How many colors do you need?
   • In 1976, mathematicians proved that you never need more than 4 colors for any flat map on Earth! (The Four Color Theorem).
2. University Exam Scheduling (Register Allocation):
   • Vertices: College courses.
   • Edges: A student is enrolled in both courses (conflict!).
   • Coloring: Time slots. Courses that conflict cannot share the same time slot. The Chromatic Number $\chi(G)$ is the absolute minimum number of exam periods needed so no student has two exams at the same time!
3. Brooks' Theorem: If every server in a network has at most 5 cables ($\Delta = 5$), you can color the entire network using at most 5 colors, unless the network is literally an all-to-all complete clique ($K_6$) or an odd cycle!

💻 Bridging to Computer Science: Compiler Register Allocation & Wireless Frequency Assignment

In computer systems:

• Compiler Register Allocation (Chaitin's Algorithm): Variables whose lifetimes overlap cannot share the same physical CPU register. Compilers construct an interference graph and $k$-color it to map hundreds of virtual variables to $k$ physical machine registers (e.g. 16 registers in x86-64).
• Cellular Tower Frequency Assignment: Adjacent cellular cell towers cannot broadcast on the same radio frequency without radio interference. $\chi(G)$ determines the minimum radio spectrum license required.
• Pattern Matching & Sudoku: A Sudoku board is a 9-coloring of a 729-edge 81-vertex graph!

📑Table of Contents

• 🎨 Proper Vertex Coloring & Chromatic Numbers
• ⚖️ Theoretical Bounds on Chromatic Numbers
• 🗺️ The Four Color Theorem for Planar Graphs
• ✂️ Edge Coloring & Vizing's Theorem
• ⚡ The Welsh-Powell Greedy Coloring Algorithm
• 📝 Step-by-Step Worked Examples
  • Example 1: Finding Chromatic Numbers of Cycle and Wheel Graphs
  • Example 2: University Exam Scheduling via Graph Coloring
• 🎯 Exam & Interview Pitfall Check

---

🎨 Proper Vertex Coloring & Chromatic Numbers

📖Definition 10.6: Proper Vertex Coloring & Chromatic Numberdefinition

1. Proper Vertex Coloring: An assignment of colors (or labels $\{1, 2, \dots, k\}$) to the vertices of a graph $G = (V, E)$ such that no two adjacent vertices share the same color: $$\{u, v\} \in E \implies c(u) \neq c(v)$$
2. $k$-Colorable: A graph is $k$-colorable if there exists a valid proper vertex coloring using at most $k$ colors.
3. Chromatic Number ($\chi(G)$): The minimum number of colors required for a proper vertex coloring of $G$: $$\chi(G) = \min \{ k \mid G \text{ is } k\text{-colorable} \}$$ A graph with $\chi(G) = k$ is said to be $k$-chromatic.

Chromatic Numbers of Standard Graph Families

Exact chromatic values across canonical symmetric graph topologies

⚪

Null Graph (No Edges)

Independent Set

• E = ∅: No two vertices are adjacent.
• Every vertex can be colored with the exact same color.
• χ(G) = 1.

🌳

Trees & Bipartite Graphs

2-Colorable

• Every tree (with |V| ≥ 2) is bipartite.
• Bipartite graphs have no odd cycles.
• χ(Tree) = 2, χ(K_{m, n}) = 2.

⭐

Complete Graph (Kₙ)

All-to-All Clique

• Every pair of vertices is connected by an edge.
• Every vertex requires a completely unique color.
• χ(Kₙ) = n.

🔄

Cycle Graph (Cₙ)

Even vs Odd Parity

• If n is EVEN (e.g. C₄, C₆): χ(Cₙ) = 2.
• If n is ODD (e.g. C₃, C₅): χ(Cₙ) = 3 (odd cycle requires 3rd color).

☸️

Wheel Graph (Wₙ)

Hub + Rim Cₙ

• Central hub connects to all rim vertices (requires unique color).
• If rim n is EVEN: χ(Wₙ) = 2 (rim) + 1 (hub) = 3.
• If rim n is ODD: χ(Wₙ) = 3 (rim) + 1 (hub) = 4.

✓ Wheel Chromatic Parity Theorem: χ(Wₙ) = 3 (if n is odd rim) vs 4 (if n is even rim)

Odd-cycle rim C₅ requires 3 colors + 1 hub = 4 colors (χ(W₅)=4); Even-cycle rim C₆ requires 2 colors + 1 hub = 3 colors (χ(W₆)=3).

---

⚖️ Theoretical Bounds on Chromatic Numbers

📐Theorem 10.12: Lower and Upper Bounds on Chromatic Numberstheorem

For any simple graph $G$:

1. Clique Lower Bound: $$\chi(G) \ge \omega(G)$$ where $\omega(G)$ is the clique number (the number of vertices in the largest complete subgraph $K_k$ contained in $G$).
2. Independence Lower Bound: $$\chi(G) \ge \frac{|V|}{\alpha(G)}$$ where $\alpha(G)$ is the independence number (the size of the largest independent set in $G$). Each color class forms an independent set with at most $\alpha(G)$ vertices.
3. Greedy Upper Bound: $$\chi(G) \le \Delta(G) + 1$$ where $\Delta(G)$ is the maximum vertex degree in $G$. In any greedy coloring, a vertex has at most $\Delta(G)$ neighbors, which leaves at least one color free among $\Delta(G) + 1$ colors.

📐Theorem 10.13: Brooks' Theorem (1941)theorem

For any connected undirected graph $G$:

$$\chi(G) \le \Delta(G)$$

unless $G$ is:

1. A Complete Graph ($K_n$, where $\chi(K_n) = \Delta + 1 = n$), or
2. An Odd Cycle ($C_{2k+1}$, where $\chi = 3 = \Delta + 1$).

For all other graphs, the chromatic number is strictly bounded by the maximum degree $\Delta(G)$!

---

🗺️ The Four Color Theorem for Planar Graphs

📐Theorem 10.14: The Four Color Theorem (Appel & Haken, 1976)theorem

Every planar graph is 4-colorable:

$$\chi(G) \le 4 \quad (\text{for all planar graphs } G)$$

• First major mathematical theorem proven with substantial computer verification: Kenneth Appel and Wolfgang Haken reduced all possible planar graphs to 1,936 reducible configurations, verifying each on an IBM 360 mainframe.
• Immediate Geographic Corollary: Any political map drawn on a flat surface or sphere can be colored using at most 4 colors such that no two adjacent territories share the same color.

The Five Color Theorem (Heawood, 1890): A simple pencil-and-paper proof exists showing that every planar graph is 5-colorable ($\chi(G) \le 5$), using Euler's formula invariant that every planar graph has at least one vertex with $\deg(v) \le 5$, followed by Kempe chain color swapping.

---

✂️ Edge Coloring & Vizing's Theorem

📖Definition 10.7: Edge Coloring & Chromatic Indexdefinition

1. Proper Edge Coloring: An assignment of colors to the edges of $G$ such that no two incident edges share the same color.
2. Chromatic Index ($\chi'(G)$): The minimum number of colors needed for a proper edge coloring of $G$.

📐Theorem 10.15: Vizing's Theorem (1964)theorem

For any simple undirected graph $G$, the chromatic index $\chi'(G)$ satisfies:

$$\Delta(G) \le \chi'(G) \le \Delta(G) + 1$$

Every simple graph falls into one of only two classes:

• Class 1: $\chi'(G) = \Delta(G)$ (e.g. all bipartite graphs, by Kőnig's Line Coloring Theorem).
• Class 2: $\chi'(G) = \Delta(G) + 1$ (e.g. odd cycles $C_{2k+1}$, complete graphs $K_{2k+1}$).

---

⚡ The Welsh-Powell Greedy Coloring Algorithm

The Welsh-Powell Algorithm provides an efficient heuristic to find near-optimal vertex colorings in $O(V^2)$ time:

The 4-Step Welsh-Powell Greedy Coloring Algorithm

Systematic degree-ordered procedure to color graphs with minimal colors

1

Sort Vertices by Descending Degree

Ordering

List all vertices in non-increasing order of their degrees: deg(v₁) ≥ deg(v₂) ≥ ... ≥ deg(vₙ).

2

Assign Current Color c to First Uncolored Vertex

Anchor

Pick the highest-degree uncolored vertex v and assign it the current color c (e.g. Color 1).

3

Greedily Propagate Color c to Non-Adjacent Vertices

Greedy Sweep

Scan down the sorted list. Assign color c to each uncolored vertex that is NOT adjacent to ANY vertex already painted with color c.

4

Advance to Next Color & Repeat

Next Color

Pick a new color (c + 1) and repeat from the top uncolored vertex until every vertex is colored.

---

📝 Step-by-Step Worked Examples

Example 1: Finding Chromatic Numbers of Cycle and Wheel Graphs

Problem Statement: Determine the chromatic number $\chi(G)$ for:

1. Cycle graph $C_5$ (Pentagon).
2. Cycle graph $C_6$ (Hexagon).
3. Wheel graph $W_5$ (Hub connected to $C_5$).
4. Wheel graph $W_6$ (Hub connected to $C_6$).

Step-by-Step Solution:

1. Cycle $C_5$ (Odd Cycle)

   • Number of vertices $n = 5$ (odd).
   • If we alternate colors Red, Blue, Red, Blue, the 5th vertex is adjacent to both the 4th vertex (Blue) and the 1st vertex (Red).
   • A 3rd color (Green) is mandatory!
   • $\chi(C_5) = 3$.

2. Cycle $C_6$ (Even Cycle)

   • Number of vertices $n = 6$ (even).
   • Alternating colors Red, Blue, Red, Blue, Red, Blue cleanly colors the cycle with zero conflicts.
   • It is bipartite!
   • $\chi(C_6) = 2$.

3. Wheel $W_5$ (Hub + $C_5$)

   • The rim is $C_5$, which requires $\chi(C_5) = 3$ colors.
   • The central hub vertex connects to every single vertex on the rim.
   • Therefore, the hub cannot share any color used by the rim, requiring an additional 4th color!
   • $\chi(W_5) = 3 + 1 = 4$.
   • $\chi(W_5) = 4$.

4. Wheel $W_6$ (Hub + $C_6$)

   • The rim is $C_6$, which requires $\chi(C_6) = 2$ colors.
   • The central hub requires a unique 3rd color.
   • $\chi(W_6) = 2 + 1 = 3$.
   • $\chi(W_6) = 3$.

Key Takeaway: Wheel graphs alternate chromatic numbers based on rim parity: odd rims require 4 colors, while even rims require 3 colors.

---

Example 2: University Exam Scheduling via Graph Coloring

Problem Statement: Five university courses ($A, B, C, D, E$) have overlapping student enrollments. Conflicting courses that share students cannot have exams at the same time:

• Course $A$ conflicts with $B, C, D$.
• Course $B$ conflicts with $A, C, E$.
• Course $C$ conflicts with $A, B, D, E$.
• Course $D$ conflicts with $A, C, E$.
• Course $E$ conflicts with $B, C, D$.

What is the minimum number of exam time slots required?

Step-by-Step Solution:

1. Step 1: Model as a Graph

   • Vertices: $\{A, B, C, D, E\}$.
   • Vertex degrees:
     • $\deg(A) = 3$ (connected to $B, C, D$)
     • $\deg(B) = 3$ (connected to $A, C, E$)
     • $\deg(C) = 4$ (connected to $A, B, D, E$)
     • $\deg(D) = 3$ (connected to $A, C, E$)
     • $\deg(E) = 3$ (connected to $B, C, D$)

2. Step 2: Identify Cliques

   • Vertices $\{A, B, C\}$ are all mutually adjacent: forms a triangle ($K_3$).
   • Are there any 4-cliques ($K_4$)?
     • Test $\{A, B, C, D\}$: Is $B$ connected to $D$? No edge exists between $B$ and $D$!
     • Test $\{A, B, C, E\}$: Is $A$ connected to $E$? No edge exists between $A$ and $E$!
     • Max clique size $\omega(G) = 3$.

3. Step 3: Apply Welsh-Powell Coloring

   • Sorted vertices by degree: $C(4), A(3), B(3), D(3), E(3)$.
   • Color 1 (Time Slot 1):
     • Assign Color 1 to highest-degree vertex: $C$.
     • Look for non-neighbors of $C$: $C$ connects to all other 4 vertices! No other vertex can take Color 1.
     • Color 1: $\{C\}$.
   • Color 2 (Time Slot 2):
     • Pick next uncolored vertex: $A$. Assign Color 2 to $A$.
     • Check non-neighbors of $A$: $E$ is not connected to $A$. Assign Color 2 to $E$.
     • (Check if $E$ can share Color 2: $E$ is not adjacent to $A$. Valid!).
     • Color 2: $\{A, E\}$.
   • Color 3 (Time Slot 3):
     • Remaining uncolored vertices: $\{B, D\}$.
     • Pick $B$. Assign Color 3 to $B$.
     • Check non-neighbors of $B$: $D$ is not connected to $B$. Assign Color 3 to $D$.
     • Color 3: $\{B, D\}$.
   • All vertices are successfully colored using 3 colors!

4. Step 4: Conclusion

   • Since $\omega(G) = 3$, $\chi(G) \ge 3$.
   • Since we found a valid 3-coloring ($\{C\}, \{A, E\}, \{B, D\}$), the chromatic number is exactly: $$\chi(G) = 3$$
   • Exactly 3 exam time slots are required.

Key Takeaway: Graph coloring models real-world conflict resolution by partitioning vertices into independent, conflict-free time slots.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If a graph has no triangles ($\omega(G) = 2$), can its chromatic number still be arbitrarily large? Key Focus Points: Yes! This was Jan Mycielski's famous discovery (1955). The Mycielski construction produces triangle-free graphs with chromatic numbers 3, 4, 5, 6, ..., and arbitrarily high! For example, the Grötzsch graph has 11 vertices, has NO triangles, yet has $\chi(G) = 4$. Having no triangles does NOT bound the chromatic number!

Question 2: Does the Four Color Theorem apply to graphs drawn on a torus (a donut shape)? Key Focus Points: No! The Four Color Theorem applies strictly to planar surfaces and spheres (genus 0). On a torus (genus 1), you can draw complete graph $K_7$ with zero edge crossings! By the Heawood conjecture, coloring maps on a torus requires up to 7 colors!

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming $\chi(G) = \omega(G)$ always holds Why it fails: $\omega(G)$ (clique number) is only a lower bound. For odd cycle $C_5$, the largest clique is an edge ($K_2$, so $\omega = 2$), but $\chi(C_5) = 3$. Never assume chromatic number equals the size of the largest complete subgraph!

Trap 2: Believing Brooks' Theorem applies to $K_n$ and odd cycles Why it fails: Complete graphs $K_n$ and odd cycles $C_{2k+1}$ are the exact two exceptions to Brooks' Theorem where $\chi(G) = \Delta(G) + 1$. For all other connected graphs, $\chi(G) \le \Delta(G)$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic10.3 Planar Graphs, Euler's Polyhedral Formula & Kuratowski's Non-Planar MinorsNext Topic →Complete Discrete Mathematics Curriculum Index