Graph Coloring: Chromatic Number Algorithms

Key Insights

Greedy coloring runs in O(V + E) time but can use up to twice the optimal colors; vertex ordering strategies like DSATUR dramatically improve practical results.
For graphs under 100 vertices, exact algorithms using branch-and-bound with DSATUR ordering can find the chromatic number in reasonable time; beyond that, you need heuristics or ILP solvers.
Special graph classes (bipartite, chordal, interval) admit polynomial-time optimal coloring—always check for exploitable structure before reaching for general-purpose algorithms.

Introduction to Graph Coloring

Graph coloring assigns labels (colors) to vertices such that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum number of colors needed. This problem appears everywhere in software systems: compiler register allocation, scheduling conflicting tasks, assigning radio frequencies without interference, and partitioning data to avoid conflicts.

Determining the chromatic number is NP-hard. Even approximating it within a factor of n^(1-ε) for any ε > 0 is NP-hard. This means we need a toolkit of approaches: exact algorithms for small instances, heuristics for large ones, and specialized algorithms when the graph has exploitable structure.

Greedy Coloring Algorithm

The greedy algorithm processes vertices in some order and assigns each vertex the smallest color not used by its neighbors. It’s fast and simple, but the result depends heavily on vertex ordering.

from collections import defaultdict

def greedy_coloring(graph: dict[int, set[int]], order: list[int] = None) -> dict[int, int]:
    """
    Greedy graph coloring.
    
    Args:
        graph: Adjacency list representation {vertex: {neighbors}}
        order: Vertex processing order (default: arbitrary)
    
    Returns:
        Mapping of vertex -> color (0-indexed)
    """
    if order is None:
        order = list(graph.keys())
    
    coloring = {}
    
    for vertex in order:
        neighbor_colors = {coloring[n] for n in graph[vertex] if n in coloring}
        
        # Find smallest available color
        color = 0
        while color in neighbor_colors:
            color += 1
        
        coloring[vertex] = color
    
    return coloring


def largest_first_order(graph: dict[int, set[int]]) -> list[int]:
    """Order vertices by decreasing degree."""
    return sorted(graph.keys(), key=lambda v: len(graph[v]), reverse=True)


def smallest_last_order(graph: dict[int, set[int]]) -> list[int]:
    """
    Smallest-last ordering: repeatedly remove minimum-degree vertex.
    Reverse the removal order for coloring.
    """
    remaining = {v: set(neighbors) for v, neighbors in graph.items()}
    order = []
    
    while remaining:
        # Find vertex with minimum degree in remaining graph
        min_vertex = min(remaining.keys(), key=lambda v: len(remaining[v]))
        order.append(min_vertex)
        
        # Remove vertex and update neighbor degrees
        for neighbor in remaining[min_vertex]:
            remaining[neighbor].discard(min_vertex)
        del remaining[min_vertex]
    
    return order[::-1]  # Reverse for coloring order

Greedy with arbitrary ordering can use up to Δ+1 colors where Δ is the maximum degree. The smallest-last ordering guarantees at most max_i(min(d_i + 1, i)) colors, where d_i is the degree when vertex i is removed. In practice, this often gets within 10-20% of optimal for sparse graphs.

Exact Algorithms for Chromatic Number

When you need the actual chromatic number, backtracking with intelligent pruning is your first tool. DSATUR (Degree of Saturation) orders vertices dynamically: always color the uncolored vertex with the most differently-colored neighbors, breaking ties by degree.

def dsatur_exact(graph: dict[int, set[int]]) -> tuple[int, dict[int, int]]:
    """
    Exact chromatic number using DSATUR with branch-and-bound.
    
    Returns:
        (chromatic_number, optimal_coloring)
    """
    n = len(graph)
    if n == 0:
        return 0, {}
    
    vertices = list(graph.keys())
    best_coloring = greedy_coloring(graph, largest_first_order(graph))
    best_num_colors = max(best_coloring.values()) + 1
    
    def saturation_degree(v: int, coloring: dict[int, int]) -> int:
        """Count distinct colors among colored neighbors."""
        return len({coloring[n] for n in graph[v] if n in coloring})
    
    def select_vertex(uncolored: set[int], coloring: dict[int, int]) -> int:
        """Select uncolored vertex with max saturation, break ties by degree."""
        return max(uncolored, key=lambda v: (saturation_degree(v, coloring), len(graph[v])))
    
    def backtrack(coloring: dict[int, int], uncolored: set[int], num_colors: int):
        nonlocal best_coloring, best_num_colors
        
        if not uncolored:
            if num_colors < best_num_colors:
                best_num_colors = num_colors
                best_coloring = coloring.copy()
            return
        
        # Pruning: can't improve on current best
        if num_colors >= best_num_colors:
            return
        
        vertex = select_vertex(uncolored, coloring)
        neighbor_colors = {coloring[n] for n in graph[vertex] if n in coloring}
        
        # Try existing colors first
        for color in range(num_colors):
            if color not in neighbor_colors:
                coloring[vertex] = color
                backtrack(coloring, uncolored - {vertex}, num_colors)
                del coloring[vertex]
        
        # Try new color only if it could improve
        if num_colors + 1 < best_num_colors:
            coloring[vertex] = num_colors
            backtrack(coloring, uncolored - {vertex}, num_colors + 1)
            del coloring[vertex]
    
    backtrack({}, set(vertices), 0)
    return best_num_colors, best_coloring

DSATUR’s dynamic ordering creates smaller search trees than static orderings. The pruning condition num_colors >= best_num_colors eliminates branches that can’t improve the solution. For random graphs under 50-70 vertices, this typically completes in under a second.

Integer Linear Programming Formulation

For medium-sized graphs (50-200 vertices), ILP solvers can outperform backtracking by exploiting sophisticated branching and cutting-plane techniques.

from ortools.linear_solver import pywraplp

def chromatic_number_ilp(graph: dict[int, set[int]], max_colors: int = None) -> tuple[int, dict[int, int]]:
    """
    Compute chromatic number using ILP.
    
    Args:
        graph: Adjacency list
        max_colors: Upper bound on colors (default: greedy result)
    
    Returns:
        (chromatic_number, coloring)
    """
    vertices = list(graph.keys())
    n = len(vertices)
    
    if max_colors is None:
        greedy_result = greedy_coloring(graph, largest_first_order(graph))
        max_colors = max(greedy_result.values()) + 1
    
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        raise RuntimeError("SCIP solver not available")
    
    # x[v][c] = 1 if vertex v has color c
    x = {}
    for v in vertices:
        x[v] = {}
        for c in range(max_colors):
            x[v][c] = solver.IntVar(0, 1, f'x_{v}_{c}')
    
    # y[c] = 1 if color c is used
    y = {c: solver.IntVar(0, 1, f'y_{c}') for c in range(max_colors)}
    
    # Each vertex gets exactly one color
    for v in vertices:
        solver.Add(sum(x[v][c] for c in range(max_colors)) == 1)
    
    # Adjacent vertices get different colors
    for v in vertices:
        for u in graph[v]:
            if u > v:  # Avoid duplicate constraints
                for c in range(max_colors):
                    solver.Add(x[v][c] + x[u][c] <= 1)
    
    # Link x and y: if vertex uses color c, then y[c] = 1
    for v in vertices:
        for c in range(max_colors):
            solver.Add(x[v][c] <= y[c])
    
    # Symmetry breaking: use colors in order
    for c in range(1, max_colors):
        solver.Add(y[c] <= y[c-1])
    
    # Minimize number of colors
    solver.Minimize(sum(y[c] for c in range(max_colors)))
    
    status = solver.Solve()
    
    if status != pywraplp.Solver.OPTIMAL:
        raise RuntimeError("No optimal solution found")
    
    coloring = {}
    for v in vertices:
        for c in range(max_colors):
            if x[v][c].solution_value() > 0.5:
                coloring[v] = c
                break
    
    return int(solver.Objective().Value()), coloring

The symmetry-breaking constraint y[c] <= y[c-1] forces colors to be used in order, eliminating equivalent solutions that differ only in color naming. This single addition can speed up solving by 10x or more.

Approximation and Heuristic Methods

For large graphs, exact methods become impractical. Tabu search maintains a “tabu list” of recent moves to escape local optima.

import random

def tabu_coloring(graph: dict[int, set[int]], num_colors: int, 
                   max_iterations: int = 10000, tabu_tenure: int = 7) -> dict[int, int] | None:
    """
    Tabu search for k-coloring. Returns coloring if found, None if not.
    
    Use binary search on num_colors to find approximate chromatic number.
    """
    vertices = list(graph.keys())
    n = len(vertices)
    
    # Random initial coloring
    coloring = {v: random.randint(0, num_colors - 1) for v in vertices}
    
    def count_conflicts(coloring: dict[int, int]) -> int:
        return sum(1 for v in vertices for u in graph[v] 
                   if u > v and coloring[v] == coloring[u])
    
    def conflicting_vertices(coloring: dict[int, int]) -> list[int]:
        return [v for v in vertices 
                if any(coloring[v] == coloring[u] for u in graph[v])]
    
    tabu = {}  # (vertex, color) -> iteration when tabu expires
    best_coloring = coloring.copy()
    best_conflicts = count_conflicts(coloring)
    
    for iteration in range(max_iterations):
        conflicts = count_conflicts(coloring)
        
        if conflicts == 0:
            return coloring
        
        if conflicts < best_conflicts:
            best_conflicts = conflicts
            best_coloring = coloring.copy()
        
        # Find best non-tabu move (or best move if it solves the problem)
        conflict_verts = conflicting_vertices(coloring)
        if not conflict_verts:
            return coloring
            
        best_move = None
        best_delta = float('inf')
        
        for v in conflict_verts:
            current_color = coloring[v]
            current_conflicts = sum(1 for u in graph[v] if coloring[u] == current_color)
            
            for new_color in range(num_colors):
                if new_color == current_color:
                    continue
                
                new_conflicts = sum(1 for u in graph[v] if coloring[u] == new_color)
                delta = new_conflicts - current_conflicts
                
                is_tabu = tabu.get((v, new_color), 0) > iteration
                aspiration = (conflicts + delta == 0)  # Solves problem
                
                if (not is_tabu or aspiration) and delta < best_delta:
                    best_delta = delta
                    best_move = (v, new_color)
        
        if best_move:
            v, new_color = best_move
            old_color = coloring[v]
            coloring[v] = new_color
            tabu[(v, old_color)] = iteration + tabu_tenure
    
    return best_coloring if count_conflicts(best_coloring) == 0 else None

To find the chromatic number approximately, binary search on the number of colors: if tabu search finds a valid k-coloring, try k-1; otherwise try k+1.

Special Graph Classes

Some graph classes admit polynomial-time optimal coloring. Chordal graphs (every cycle of 4+ vertices has a chord) can be colored optimally using a perfect elimination ordering.

def is_chordal_and_color(graph: dict[int, set[int]]) -> tuple[bool, dict[int, int] | None]:
    """
    Check if graph is chordal; if so, return optimal coloring.
    Uses maximum cardinality search for perfect elimination ordering.
    """
    vertices = list(graph.keys())
    n = len(vertices)
    
    if n == 0:
        return True, {}
    
    # Maximum cardinality search
    order = []
    weights = {v: 0 for v in vertices}
    remaining = set(vertices)
    
    for _ in range(n):
        v = max(remaining, key=lambda x: weights[x])
        order.append(v)
        remaining.remove(v)
        for u in graph[v]:
            if u in remaining:
                weights[u] += 1
    
    order.reverse()  # Perfect elimination ordering
    position = {v: i for i, v in enumerate(order)}
    
    # Verify chordality: for each vertex, its earlier neighbors must form a clique
    for v in order:
        earlier_neighbors = [u for u in graph[v] if position[u] < position[v]]
        for i, u in enumerate(earlier_neighbors):
            for w in earlier_neighbors[i+1:]:
                if w not in graph[u]:
                    return False, None
    
    # Color using reverse elimination order (greedy is optimal for chordal)
    coloring = {}
    for v in reversed(order):
        neighbor_colors = {coloring[u] for u in graph[v] if u in coloring}
        color = 0
        while color in neighbor_colors:
            color += 1
        coloring[v] = color
    
    return True, coloring

Bipartite graphs have chromatic number 2 (detectable via BFS). Interval graphs are chordal, so the above algorithm applies. Always check for special structure first—it can reduce an NP-hard problem to linear time.

Practical Considerations and Benchmarks

Choose your algorithm based on graph characteristics:

Graph Size	Density	Recommended Approach
< 50 vertices	Any	DSATUR exact
50-200 vertices	Sparse	ILP with symmetry breaking
50-200 vertices	Dense	DSATUR with aggressive pruning
200+ vertices	Any	Tabu search or genetic algorithms
Any	Special structure	Specialized polynomial algorithm

For production use, leverage existing libraries. NetworkX provides greedy_color() with multiple strategies. For ILP, Google OR-Tools or Gurobi handle the heavy lifting. The igraph library offers efficient C implementations.

When benchmarking, use standard instances from the DIMACS graph coloring challenge. Random graphs are poor benchmarks—real-world graphs have structure that algorithms can exploit.

The key insight: chromatic number computation is about matching algorithm complexity to problem size. Start with greedy for a quick upper bound, check for special structure, then escalate to exact or heuristic methods as needed.