Graph Coloring: Concepts and Applications
Learn about graph coloring, chromatic number, greedy coloring algorithms, and real-world applications in scheduling, register allocation, and map coloring.
Detailed Explanation
Graph Coloring
Graph coloring assigns colors (or labels) to vertices such that no two adjacent vertices share the same color. The minimum number of colors needed is the chromatic number χ(G).
Greedy Coloring Algorithm
- Order the vertices (the ordering affects the result)
- For each vertex, assign the smallest color not used by any of its already-colored neighbors
Order: A, B, C, D
A → color 1
B (neighbor of A) → color 2
C (neighbor of A, B) → color 3
D (neighbor of B, C) → color 1 (not adjacent to A)
Chromatic Number
- Trees: χ = 2 (always bipartite)
- Cycles: χ = 2 (even length) or 3 (odd length)
- Complete graph K_n: χ = n
- Planar graphs: χ ≤ 4 (Four Color Theorem)
NP-Completeness
Determining the exact chromatic number is NP-hard for general graphs. The greedy algorithm gives an upper bound but not always the optimal coloring. Various heuristics and backtracking approaches are used in practice.
Applications
- Map coloring — Color regions so adjacent regions differ (the Four Color Theorem guarantees 4 colors suffice for any planar map)
- Register allocation — Compilers assign variables to CPU registers; conflicting variables (used simultaneously) cannot share a register
- Scheduling — Exams, meetings, or tasks that conflict need different time slots (colors)
- Frequency assignment — Radio towers need different frequencies if their ranges overlap
k-Colorability and Bipartiteness
A graph is 2-colorable if and only if it is bipartite. Testing 2-colorability is O(V + E), but testing 3-colorability is already NP-complete.
Use Case
Compiler backends use graph coloring for register allocation — the most widely used algorithm (Chaitin's algorithm) builds an interference graph and colors it. Cell phone networks use graph coloring to assign frequencies to towers without interference. University exam scheduling uses coloring to prevent exam conflicts. Sudoku can be modeled as a graph coloring problem on a constraint graph.