Graph Coloring Deep Dive

Graph coloring assigns colors to graph vertices so that adjacent vertices have different colors. The chromatic number χ(G) is the minimum number of colors needed.

It looks like a puzzle problem; it's also the abstract structure behind register allocation, scheduling, frequency assignment, and timetabling.

The basic problem

Given an undirected graph G = (V, E), color each vertex such that no two adjacent vertices share a color. Minimize the number of colors used.

Examples

Path graph

Two colors suffice (alternate). χ = 2.

Cycle

- Even cycle: χ = 2

- Odd cycle: χ = 3

Complete graph K_n

All pairs adjacent. χ = n.

Bipartite graph

Two-colorable (one color per side). χ = 2.

A graph is bipartite iff it has no odd cycles.

Planar graphs

By the Four Color Theorem (1976): every planar graph is 4-colorable.

The proof was the first major theorem proven by computer.

Complexity

Decision problem

"Is G k-colorable?"

- 2-colorability: O(n + m), polynomial

- 3-colorability: NP-complete

- k-colorability for k ≥ 3: NP-complete

Optimization

Computing χ(G) is NP-hard.

Approximating χ(G) is also hard. There's no polynomial algorithm with reasonable approximation ratio under standard complexity assumptions.

In practice: heuristics dominate.

Heuristic algorithms

Greedy

Order vertices; color each with smallest available color.

Quality depends on order:

- Smallest-degree last

- Largest-degree first (often called Welsh-Powell)

- Random

Greedy is fast but can use much more than χ colors.

DSATUR (Degree of Saturation)

At each step, color the vertex with most distinct neighbor colors. Tie-break by degree.

Often produces near-optimal colorings.

Backtracking

Try colors; backtrack on conflict. Optimal but exponential.

For small graphs (~30 vertices), works fine.

Local search

Start with a coloring; try recoloring conflicting vertices.

Tabu search and simulated annealing variants are common.

Integer linear programming

Encode as ILP; solve with commercial solvers (Gurobi, CPLEX).

Practical for moderate graphs.

Variants

Edge coloring

Color edges so adjacent edges (sharing a vertex) differ.

Vizing's theorem: χ'(G) is Δ or Δ+1, where Δ is max degree.

Edge coloring is also NP-hard but has tighter bounds.

List coloring

Each vertex has a list of allowed colors. Find proper coloring respecting lists.

Choosability ch(G) ≥ χ(G).

Interval coloring

Each vertex represents an interval; coloring the interval graph.

Equivalent to scheduling on machines.

Total coloring

Color both vertices and edges; adjacent or incident things differ.

Online coloring

Vertices arrive one at a time; must color immediately.

Quality bounds are weaker than offline.

Applications

In compilers: variables that are simultaneously live are adjacent in the interference graph. Color = register.

If χ ≤ number of registers, all variables fit.

If not: spill some to memory.

This is one of the original motivations for graph coloring research.

Scheduling

Tasks that conflict (need same resource at same time) are adjacent. Color = time slot.

Course timetabling: courses with shared students conflict.

Exam scheduling: same logic.

Frequency assignment

Cell towers that interfere are adjacent. Color = frequency.

Reduces interference.

Sudoku

A Sudoku puzzle is graph coloring with 9 colors on a specific 81-vertex graph.

Map coloring

Original motivation. Adjacent regions get different colors.

Four colors suffice for any planar map.

Practical algorithms

For real-world coloring:

Small graphs (< 100 vertices)

Backtracking finds optimum.

Medium graphs (100s-1000s)

DSATUR + local search.

Large graphs

Greedy + local search.

Specific structures

Some graph classes have polynomial algorithms:

- Bipartite (matching algorithms work)

- Chordal (perfect elimination ordering)

- Interval graphs

- Trees

Lower bounds

Bounds on χ(G):

Clique number ω(G)

χ(G) ≥ ω(G). The largest clique requires that many colors.

For perfect graphs, equality. In general, can be much higher.

Fractional chromatic number χ_f(G)

A relaxation. χ_f ≤ χ.

Chromatic polynomial

Counts the number of proper k-colorings.

Upper bounds

Brooks' theorem

For connected G that is not complete or odd cycle: χ(G) ≤ Δ(G) (max degree).

Greedy with smart ordering

For graph with degree sequence d₁ ≥ d₂ ≥ ... ≥ d_n: greedy uses at most max_i min(d_i + 1, i) colors.

Practical insight: structure matters

Real-world graphs often have structure that helps:

- Sparse, irregular: heuristics work well

- Bipartite: 2 colors

- Tree-like: low chromatic number

- Random: known asymptotic behavior

The hard cases are dense, irregular, adversarial graphs.

Common failure patterns

Treating as solvable optimally

For large graphs, χ(G) is usually impossible to find exactly.

Wrong heuristic for instance type

Greedy fails on adversarial inputs. DSATUR usually robust.

Ignoring problem structure

If your problem has structure (interval graph, bipartite), use specialized algorithms.

Over-engineering

Simple greedy often suffices. Get baseline before complex methods.

Connection to other problems

Independent set

Each color class is an independent set. Coloring = partition into independent sets.

Clique cover

Coloring complement = clique cover.

Vertex cover

Related but different. Both NP-hard.

Specific software

- **NetworkX** (Python): basic algorithms

- **Boost Graph Library** (C++): more

- **Gurobi/CPLEX**: ILP-based exact methods

- **Specific solvers**: research code

For most applications, NetworkX greedy + local search suffices.

Why this matters

Understanding graph coloring teaches:

- NP-hardness in a concrete setting

- The gap between theory (NP-hard) and practice (heuristics work)

- How abstract problems map to applications

- Heuristic algorithm design

The applications (register allocation, scheduling) are practical and important.