Perfect Graphs, in depth: χ = ω on every induced subgraph, the strong perfect graph theorem and polynomial coloring

Clique number, chromatic number and perfection

Let G be an undirected graph. Its clique number ω(G) is the size of the largest set of pairwise adjacent vertices. Its chromatic number χ(G) is the fewest colors such that adjacent vertices differ. Every vertex in a clique needs its own color, so χ(G) ≥ ω(G) always.

The gap can be large: there are triangle-free graphs (ω = 2) with arbitrarily high chromatic number. The smallest example of any gap is the 5-cycle C5. Its largest clique is an edge, so ω = 2, but an odd cycle cannot be 2-colored, so χ = 3.

An induced subgraph keeps a subset of vertices and every edge between them. A graph is perfect if χ(H) = ω(H) for every induced subgraph H, including G itself. The 'every induced subgraph' part matters: adding a large clique next to C5 gives a graph whose χ equals ω, but it is not perfect, because C5 is still sitting inside it.

The same idea applies to the complementary pair of problems. The independence number α(G) is the size of the largest set of pairwise non-adjacent vertices, and the clique cover number is the fewest cliques that together cover all vertices. Every clique holds at most one vertex of an independent set, so the cover number is at least α. In the complement graph, cliques and independent sets swap roles.

The two perfect graph theorems

Claude Berge introduced perfect graphs around 1960 together with two conjectures, and both are now theorems.

Weak perfect graph theorem (Lovász, 1972): a graph is perfect if and only if its complement is perfect. Equivalently, if χ = ω on every induced subgraph, then the clique cover number equals α on every induced subgraph. One theorem gives two min-max relations for free.

Strong perfect graph theorem (Chudnovsky, Robertson, Seymour and Thomas; announced 2002, published in the Annals of Mathematics in 2006): a graph is perfect if and only if it contains no odd hole and no odd antihole. An odd hole is an induced cycle of odd length at least 5; an odd antihole is the complement of one. Graphs with neither are called Berge graphs. C5 is its own complement, so it is both; the next forbidden shapes are C7 and its complement, and so on.

Two algorithmic facts complete the picture. Recognising perfect graphs is polynomial: Chudnovsky, Cornuéjols, Liu, Seymour and Vušković gave an algorithm in 2005, roughly O(n^9). Finding an odd hole on its own was a long-standing open problem, solved in polynomial time by Chudnovsky, Scott, Seymour and Spirkl in 2020. Both algorithms are far too slow and intricate for everyday use; in practice you prove perfection by knowing which class your graph belongs to.

The perfect families

Each row is a classical min-max theorem in disguise. Perfection is the umbrella that explains why they all hold at once, and the weak theorem explains why each class's complement is just as well behaved: Dilworth's theorem about antichains, for example, is the complement of Mirsky's.

Testing perfection on small graphs

The strong theorem turns 'check every induced subgraph' into 'look for two shapes'. On small graphs, a direct search is the clearest way to test a hypothesis, build test fixtures or check a reduction. It is exponential, so keep n under about 20.

from itertools import combinations

def complement(adj):
    n = len(adj)
    return [set(range(n)) - adj[v] - {v} for v in range(n)]

def is_induced_cycle(adj, S):
    S = set(S)
    if any(len(adj[v] & S) != 2 for v in S):   # every vertex: exactly 2 neighbours inside S
        return False
    start = next(iter(S))
    seen, stack = {start}, [start]
    while stack:                                # connected + 2-regular = one cycle
        v = stack.pop()
        for u in adj[v] & S:
            if u not in seen:
                seen.add(u)
                stack.append(u)
    return seen == S

def find_odd_hole(adj):
    n = len(adj)
    for k in range(5, n + 1, 2):
        for S in combinations(range(n), k):
            if is_induced_cycle(adj, S):
                return S
    return None

def is_perfect_small(adj):
    """Strong perfect graph theorem, by brute force. adj: list of sets."""
    return find_odd_hole(adj) is None and find_odd_hole(complement(adj)) is None

c5 = [{1, 4}, {0, 2}, {1, 3}, {2, 4}, {3, 0}]
assert not is_perfect_small(c5)

A useful habit: when you believe a graph you build in production is in a perfect class, generate small random instances and run this check in a property-based test. It catches modelling mistakes, such as an extra edge type, that quietly break the structure the fast algorithm relies on.

Lovász theta: the polynomial route

For perfect graphs in general, the polynomial algorithms come from Grötschel, Lovász and Schrijver in the early 1980s. They are not combinatorial: they rest on the Lovász theta function θ, which can be computed to any desired precision by semidefinite programming (they used the ellipsoid method; interior-point solvers are the practical choice today). Theta is sandwiched:

alpha(G)  <=  theta(G)  <=  clique cover number of G
omega(G)  <=  theta(complement G)  <=  chi(G)       # the "sandwich theorem"

When G is perfect, the outer quantities are equal, so θ is squeezed to an integer and rounding the SDP value gives ω or α exactly. One standard formulation, with X a symmetric matrix:

import cvxpy as cp

def theta(adj):
    """Lovász theta: maximise sum(X) s.t. trace(X) = 1, X_ij = 0 on edges, X PSD."""
    n = len(adj)
    X = cp.Variable((n, n), symmetric=True)
    cons = [X >> 0, cp.trace(X) == 1]
    cons += [X[i, j] == 0 for i in range(n) for j in adj[i] if i < j]
    prob = cp.Problem(cp.Maximize(cp.sum(X)), cons)
    prob.solve()
    return prob.value

def clique_number_perfect(adj, tol=1e-3):
    t = theta(complement(adj))                 # omega(G) = alpha(complement G)
    k = round(t)
    if abs(t - k) > tol:
        raise ValueError(f"theta={t:.4f} is not near an integer: graph is not perfect?")
    return k

On C5 the value is √5 ≈ 2.236, strictly between α = 2 and the cover number 3; a non-integer theta is a certificate that the graph is not perfect. Theta gives the number, not the clique itself; to find one, delete vertices one at a time and keep each deletion that leaves the value unchanged, which costs n more SDP solves. Coloring a general perfect graph in polynomial time also goes through this machinery and is more involved. As of this writing, no purely combinatorial polynomial coloring algorithm is known for all perfect graphs, though there are combinatorial algorithms for bounded clique number and for most named subclasses.

Chordal graphs: optimal coloring in one pass

The everyday case is a chordal graph, and there the algorithm is simple. A graph is chordal if every cycle of length four or more has a chord. Chordal graphs have a perfect elimination ordering: an order in which each vertex's later neighbours form a clique. Maximum cardinality search (MCS, Tarjan and Yannakakis) finds one: repeatedly visit the unvisited vertex with the most visited neighbours. The reverse of the visit order is a perfect elimination ordering if and only if the graph is chordal, so the same pass also recognises chordality.

Color greedily in visit order. When a vertex is colored, its already colored neighbours form a clique, so the vertex needs at most one color more than that clique has. No vertex ever needs more than ω colors, and since χ ≥ ω, the result is optimal.

from itertools import combinations

def mcs_order(adj):
    n = len(adj)
    weight, visited, order = [0] * n, [False] * n, []
    for _ in range(n):           # O(n^2); bucket queues make it O(n + m)
        v = max((u for u in range(n) if not visited[u]), key=lambda u: weight[u])
        visited[v] = True
        order.append(v)
        for u in adj[v]:
            if not visited[u]:
                weight[u] += 1
    return order

def color_chordal(adj):
    order = mcs_order(adj)
    pos = {v: i for i, v in enumerate(order)}
    color = {}
    for v in order:
        earlier = [u for u in adj[v] if pos[u] < pos[v]]
        if any(b not in adj[a] for a, b in combinations(earlier, 2)):
            raise ValueError("not chordal: earlier neighbours of %d are not a clique" % v)
        used = {color[u] for u in earlier}
        color[v] = min(c for c in range(len(earlier) + 1) if c not in used)
    return color             # number of colors == clique number

Worked example: coloring a chordal graph

Take six vertices a to f with edges ab, ac, bc, bd, cd, ce, de and ef. It contains three triangles (abc, bcd, cde) and a pendant edge ef. Both 4-cycles, a-b-d-c and b-d-e-c, have chords (bc and cd), so the graph is chordal and ω = 3. Run MCS with ties broken alphabetically:

Every set of earlier neighbours is a clique, so the check passes, and three colors are used. The largest earlier-neighbour set plus the vertex itself (step 3: a, b, c) is a maximum clique, found for free. Now add a single edge from a to e. The cycle a-b-d-e has no chord, and when e is visited its earlier neighbours are a, c and d, where a and d are not adjacent, so the code raises instead of returning a coloring that might be wrong.

Where perfect graphs show up

• Room and resource allocation. Jobs with start and end times form an interval graph. The fewest rooms equals the maximum number of jobs overlapping at one instant: sort by start and reuse a room as soon as it frees up.
• Register allocation. Programs in SSA form have chordal interference graphs, a result shown in the mid-2000s by several groups including Hack, Grund and Goos. Allocators use this to color optimally and to separate spilling decisions from assignment.
• Scheduling with precedence. Tasks under a partial order form a comparability graph; the longest chain bounds the fewest parallel stages.
• Integer programming. The clique constraints of a perfect graph describe the convex hull of its independent sets exactly, so the LP relaxation already has integral optima; solvers exploit this structure in conflict graphs.

Failure modes

• Assuming the class without checking. One extra edge type can create an odd hole. Validate the structure (the MCS check above costs nothing extra) or test small instances.
• Greedy in an arbitrary order. Perfection does not make every greedy order optimal. On a bipartite crown graph, a bad order makes greedy use n/2 colors instead of 2.
• Treating perfect as easy for everything. Perfection buys clique, coloring, independent set and clique cover. Hamiltonian cycle stays NP-complete even on split graphs, which are chordal.
• SDP tolerance. Solvers return approximate values. Round with a tolerance, and treat a value far from an integer as evidence the input is not perfect, not as noise.
• Brute force in production. The odd-hole search is exponential; it belongs in tests.

What to do next

1. Check C5 by hand: write down ω, χ and α, and confirm the gap.
2. Run is_perfect_small on random graphs from a class you use; confirm it never finds an odd hole.
3. Implement mcs_order with bucket queues for O(n + m) and color a graph of 100,000 intervals.
4. Install cvxpy, compute theta for C5 and for a bipartite graph, and compare with α.
5. Look for a perfect class hidden in one of your own problems: overlaps, precedences or conflicts.
6. Keep learning: general graph coloring heuristics, why clique is NP-hard in general, König's theorem in bipartite graphs and testing bipartiteness with BFS.