Graph Coloring

Definition

A proper k-coloring of a graph G assigns one of k colors to each vertex such that no two adjacent vertices share a color.

The chromatic number χ(G) is the smallest k for which a proper k-coloring exists.

Equivalent definition — partition vertices into k independent sets (sets with no edges within them). Each independent set gets one color.

Examples:

• Empty graph (no edges) — χ = 1.
• Bipartite graph — χ = 2.
• Triangle K₃ — χ = 3.
• Complete graph Kₙ — χ = n.
• Cycle C₅ (pentagon) — χ = 3 (odd cycle).
• Cycle C₆ (hexagon) — χ = 2 (even cycle, bipartite).

Standard bounds

Bound	Statement	Notes
Trivial lower	χ(G) ≥ ω(G)	ω = clique number; cliques need distinct colors
Greedy upper	χ(G) ≤ Δ(G) + 1	Δ = max degree; achievable by greedy algorithm
Brooks (1941)	χ(G) ≤ Δ(G), except Kₙ and odd cycles	Tightens greedy bound for most graphs
Four Color Theorem	χ(G) ≤ 4 if G planar	Appel-Haken 1976, computer-assisted
Heawood (1890)	χ(G) ≤ ⌊(7 + √(1 + 48g))/2⌋ on genus-g surface	For surface non-planar; tight for g ≥ 1
Vizing edge coloring	χ'(G) ≤ Δ(G) + 1	Edge coloring (chromatic index)

The Four Color Theorem

Every planar graph (graph drawable in the plane without crossings) can be properly colored with at most 4 colors.

History:

• Conjectured 1852 by Francis Guthrie (color map of England's counties, noticed 4 always sufficed).
• Heawood (1890) proved 5-color theorem with simpler argument.
• Appel and Haken (1976) proved 4-color theorem using computer-aided case analysis — checking ~1936 reducible configurations.
• Robertson, Sanders, Seymour, Thomas (1996) gave simpler computer-assisted proof.
• Gonthier (2005) formally verified the proof in the Coq proof assistant.

The theorem says every map (with regions = countries, edges = adjacencies) can be colored using only 4 colors. Generalizations to higher-genus surfaces give different bounds (Heawood's formula).

Greedy coloring algorithm

Order vertices v₁, v₂, ..., vₙ. For each vertex in turn:

1. Look at colors of already-colored neighbors.
2. Assign vertex the smallest color not used by neighbors.

Since each vertex has at most Δ(G) neighbors, at most Δ(G) colors are blocked, so a color in {1, ..., Δ + 1} is always available. Therefore χ(G) ≤ Δ(G) + 1.

Greedy is fast (linear in size of graph) but not optimal. Different orderings give different colorings. Welsh-Powell algorithm orders by descending degree — often gives better results.

Bipartite — when 2 colors suffice

A graph is bipartite if its vertices can be partitioned into two independent sets — equivalently, if it's 2-colorable.

König's theorem — A graph is bipartite if and only if it has no odd cycles.

Algorithm — BFS from any vertex, alternate colors at each BFS level. If you ever try to color a vertex differently from how it's already colored, an odd cycle exists and the graph isn't bipartite.

Bipartite testing is in P (linear time). 3-coloring is already NP-hard.

Real-world applications

Register allocation in compilers

Variables in a program become vertices. Two variables are connected if their live ranges overlap (used at the same time). The graph's chromatic number = minimum CPU registers needed without spilling to memory.

Chaitin's register allocation algorithm — build interference graph, color with k = number of registers, "spill" vertices that can't be colored. Critical for compiler optimization.

Scheduling

Events become vertices. Conflicting events (same room, same person, etc.) are connected. Colors = time slots. Minimum number of slots = chromatic number.

Examples — exam scheduling, conference talks, employee shifts.

Frequency assignment

Radio/cell towers become vertices. Connect towers whose ranges overlap (would interfere). Colors = frequencies. Want fewest distinct frequencies. Same coloring problem.

Sudoku

Sudoku is graph coloring on an 81-vertex graph (one per cell), with edges between cells in the same row, column, or 3×3 box. Needs exactly 9 colors. Each Sudoku puzzle is a partial coloring; solving = completing it.

JavaScript — graph coloring

// Graph as adjacency list: { v: [neighbors] }

// Greedy coloring — simple ordering
function greedyColoring(graph) {
  const colors = {};
  const vertices = Object.keys(graph);
  for (const v of vertices) {
    const neighborColors = new Set(
      (graph[v] || []).map(n => colors[n]).filter(c => c !== undefined)
    );
    let c = 0;
    while (neighborColors.has(c)) c++;
    colors[v] = c;
  }
  return colors;
}

// Welsh-Powell: order by descending degree
function welshPowell(graph) {
  const sortedVertices = Object.keys(graph).sort(
    (a, b) => (graph[b]?.length || 0) - (graph[a]?.length || 0)
  );
  const colors = {};
  for (const v of sortedVertices) {
    const neighborColors = new Set(
      (graph[v] || []).map(n => colors[n]).filter(c => c !== undefined)
    );
    let c = 0;
    while (neighborColors.has(c)) c++;
    colors[v] = c;
  }
  return colors;
}

// Test: triangle K₃
const triangle = {
  A: ['B', 'C'],
  B: ['A', 'C'],
  C: ['A', 'B']
};
console.log(greedyColoring(triangle)); // {A: 0, B: 1, C: 2} (3 colors, as needed)

// Test: cycle C₆ (bipartite)
const c6 = {
  '0': ['1', '5'], '1': ['0', '2'], '2': ['1', '3'],
  '3': ['2', '4'], '4': ['3', '5'], '5': ['4', '0']
};
console.log(greedyColoring(c6));  // alternating 0, 1 (2 colors)

// Bipartite test via BFS
function isBipartite(graph) {
  const colors = {};
  const vertices = Object.keys(graph);
  for (const start of vertices) {
    if (colors[start] !== undefined) continue;
    const queue = [start];
    colors[start] = 0;
    while (queue.length) {
      const v = queue.shift();
      for (const n of (graph[v] || [])) {
        if (colors[n] === undefined) {
          colors[n] = 1 - colors[v];
          queue.push(n);
        } else if (colors[n] === colors[v]) {
          return false;  // adjacent same color = odd cycle
        }
      }
    }
  }
  return true;
}

console.log(isBipartite(c6));      // true (even cycle)
console.log(isBipartite(triangle)); // false (triangle = odd cycle)

Where graph coloring shows up

• Compiler register allocation. Map program variables to CPU registers using interference graph coloring. Chaitin-Briggs algorithm, used in GCC, LLVM, others.
• Scheduling problems. Exams, classes, conferences, employee shifts. NP-hard in general, but heuristics like Welsh-Powell work well.
• Frequency assignment. Cell towers, WiFi channels, radio broadcasting. Adjacent regions need distinct frequencies.
• Map coloring. Geographic maps colored so adjacent regions differ. Four Color Theorem says 4 always suffice.
• Sudoku and puzzles. Sudoku is a 9-coloring problem. Other "constraint satisfaction" puzzles often reduce to coloring.
• Theoretical CS. Coloring is canonical NP-hard problem; many problems reduce to (or from) coloring.
• Bioinformatics. Sequence assembly, conflict graphs. Coloring assigns parts to non-overlapping experiments.

Common mistakes

• Confusing chromatic number with maximum degree. χ ≤ Δ + 1, but often χ ≪ Δ + 1. A bipartite graph with Δ = 100 still has χ = 2.
• Forgetting bipartite ↔ no odd cycles. Some try to 2-color a graph and fail because of an odd cycle they didn't notice. Always check via BFS/DFS.
• Believing greedy is optimal. Greedy depends on vertex ordering; bad orderings give bad colorings. Welsh-Powell (descending degree) usually better but not optimal.
• Mixing up vertex and edge coloring. Vertex coloring — adjacent vertices differ; chromatic number χ. Edge coloring — adjacent edges differ; chromatic index χ' ≤ Δ + 1 (Vizing). Different problems.
• Trying to compute χ exactly for huge graphs. NP-hard. For practical large graphs, use heuristics (Welsh-Powell, DSATUR) or approximations.
• Forgetting the four-color theorem requires planarity. Non-planar graphs can need many more colors; Kₙ requires n. Four-color is special to planar graphs.