Chromatic Number and Chromatic Polynomial, in depth: closing the bounds gap, inclusion-exclusion in O*(2^n), and reductions that shrink n

Hardness and the bounds you start with

Deciding whether χ(G) <= 3 is NP-complete, even for planar graphs of maximum degree 4. Approximation does not rescue you: Zuckerman (2007) showed that approximating χ within a factor n^(1 - ε), for any ε > 0, is NP-hard. So for general graphs an exact answer means exponential time, and the engineering question becomes how small you can make the exponent's base and the n it applies to.

In practice you sandwich χ between a lower bound L and an upper bound U. If L = U you are done and never run an exact algorithm. The cheap bounds are:

Brooks' theorem says χ <= Δ, the maximum degree, for every connected graph other than a complete graph or an odd cycle. The clique bound is the one people reach for, and the one with the worst blind spot. Mycielski's construction builds triangle-free graphs, so ω = 2, with arbitrarily large χ.

When the bounds do not meet: the Grötzsch graph

Apply Mycielski's construction once to the 5-cycle and you get the Grötzsch graph: 11 vertices, 20 edges, no triangles. The code below measured its bounds: ω = 2, independence number α = 5 so ceil(11 / 5) = 3, DSATUR uses 4 colours, and Δ = 5. The lower bounds stop at 3 and the upper bounds start at 4. Nothing cheap tells you which is right. The exact algorithm says χ = 4, so DSATUR was optimal and every lower bound was loose.

On the Petersen graph, with 10 vertices, ω = 2 but α = 4, so ceil(10 / 4) = 3 matches DSATUR's 3 and you are done without exact search. That is the common case. The exact algorithm is for when it is not.

Inclusion-exclusion: counting covers by independent sets

The idea is to count, not search. Let i(S) be the number of independent sets inside the vertex subset S, the empty set included. Then define

c_k(G) = sum over all subsets S of V of (-1)^(n - |S|) * i(S)^k

By inclusion-exclusion, c_k counts ordered k-tuples of independent sets whose union is all of V. The term i(S)^k counts k-tuples drawn inside S, and the alternating signs cancel every tuple that misses some vertex. A cover by k independent sets exists exactly when a proper k-colouring exists: shrink overlapping sets until they are disjoint, and give each set its own colour. So χ(G) <= k exactly when c_k(G) > 0.

Check it by hand on a triangle. The empty set holds 1 independent set, each single vertex 2, each pair 3 (the pair itself is an edge, so it is not independent), and the whole triangle 4. Then c_k = 4^k - 3 * 3^k + 3 * 2^k - 1. At k = 2 that is 16 - 27 + 12 - 1 = 0, so two colours are impossible. At k = 3 it is 64 - 81 + 24 - 1 = 6: the six ways to put one vertex in each of three ordered classes, which here equals P(K3, 3) = 3!. Nothing was searched; the zero came from arithmetic.

All 2^n values of i(S) come from one recurrence. Pick any vertex v in S. Independent sets in S either avoid v, giving i(S - v), or contain v and avoid its neighbours, giving i(S - v - N(v)). With bitmasks that is one line per subset:

def chromatic_number(n, edges):
    """Smallest k with c_k > 0. O(2^n) prep, O(2^n) big-int work per k."""
    if n == 0:
        return 0
    nb = [0] * n
    for u, v in edges:
        nb[u] |= 1 << v
        nb[v] |= 1 << u
    ind = [1] + [0] * ((1 << n) - 1)        # ind[S] = independent sets in S
    for S in range(1, 1 << n):
        v = (S & -S).bit_length() - 1       # lowest vertex in S
        rest = S & ~(1 << v)
        ind[S] = ind[rest] + ind[rest & ~nb[v]]
    sign = [(-1) ** (n - bin(S).count("1")) for S in range(1 << n)]
    for k in range(1, n + 1):
        if sum(sign[S] * ind[S] ** k for S in range(1 << n)) > 0:
            return k
    return n

Björklund, Husfeldt and Koivisto (2009) showed that this gives O*(2^n) time, 2^n times a polynomial factor. Since χ <= n you can binary search on k rather than scan, and in practice you start at your lower bound. For the Grötzsch graph the whole vertex set contains 103 independent sets, c_3 = 0 and c_4 = 163,680, which proves χ = 4 in about 2 milliseconds. The c_3 = 0 is a certificate of impossibility that no amount of failed search could give you.

How the count relates to P(G, k)

c_k is not P(G, k). The chromatic polynomial counts colourings: functions from vertices to k colours, which are partitions into at most k labelled classes. c_k counts covers, which may overlap and include empty sets, so c_k is always at least P(G, k). Both vanish below χ and are positive from χ upward, and that is all the decision needs. For the Grötzsch graph, brute force over every colouring gives P(G, 3) = 0 and P(G, 4) = 12,480, against c_4 = 163,680.

The same paper also computes the full chromatic polynomial in O*(2^n) time, but you rarely need it. Use the polynomial when the question is genuinely about counts, for example the probability that a random k-colouring is proper, which is P(G, k) / k^n, or for reliability-style questions. Use the decision test when the question is how many colours you need.

Subset DP, and measured scaling

An older approach is dynamic programming over subsets. Let X[S] be the chromatic number of the subgraph induced by S. Some colour class contains the lowest vertex v of S, so X[S] = 1 + min X[S - I] over independent sets I in S that contain v. Lawler's 1976 algorithm restricts I to maximal independent sets and proves an O(2.4423^n) bound. The simpler version that enumerates every independent set containing v is easier to write, and it agreed with inclusion-exclusion and with brute force on 300 random graphs of up to 7 vertices. On the Grötzsch graph it took 7 milliseconds against 2 for inclusion-exclusion. The DP's advantage is that it yields an optimal colouring directly, by recording the chosen I; inclusion-exclusion only says yes or no, so you then recover a colouring by search with k fixed.

Scaling for inclusion-exclusion in CPython, on random graphs with edge probability 0.5: n = 16 in 0.08 seconds, n = 18 in 0.95 and n = 20 in 4.2. Each step of two in n multiplied the time by between about four and twelve, because both the 2^n table and the size of the big integers grow. A compiled implementation that works modulo a large prime is far faster, and then memory becomes the wall: with 8-byte entries the i(S) table alone is 8 GiB at n = 30. A nonzero residue proves c_k is nonzero, but a zero residue only suggests it, because c_k might be a multiple of the prime. Confirm a zero with a second prime or exact arithmetic before you report that k colours are impossible.

Reductions that shrink n

Exponential algorithms reward every vertex you remove first. Four reductions are exact:

• Components. χ is the maximum over connected components; P is the product.
• Blocks. For a graph with at least one edge, χ is the maximum over its biconnected components. For a connected graph, P is the product of the block polynomials divided by k for each cut-vertex gluing. Two triangles sharing a vertex give P = (k(k - 1)(k - 2))^2 / k, which is 12 at k = 3; the code confirmed the identity for k = 1 to 5 by brute force.
• Clique cutsets. If G is two graphs glued along a clique K_r, then P(G) = P(G1) P(G2) / P(K_r), and χ is the larger of the two parts' values.
• Low-degree peeling. When testing k-colourability, a vertex of degree below k can always be coloured last, so delete it and repeat. What remains is the k-core, often far smaller than the graph.

Some graph classes need no exponential work at all. In perfect graphs χ equals ω, and interval graphs are perfect, so sorting by start time and colouring greedily is optimal. Bipartite graphs need 2 colours, checked by BFS. For the clique bound itself, see maximum clique.

Operational guidance

1. Split into components and blocks, and peel low-degree vertices for the k you are testing.
2. Compute a lower bound: a clique from greedy or branch and bound, and ceil(n / α) if an independence number is affordable.
3. Run DSATUR for an upper bound and a concrete colouring.
4. If the bounds meet, stop. Otherwise run inclusion-exclusion on the remaining pieces with n up to about 20 in Python, or hand larger pieces to a SAT or integer programming solver with a time limit.
5. Log which step produced the answer. A colouring with a proof of optimality is a different product from a colouring that merely looks good.

Failure modes

• Trusting ω. Reporting "optimal" because the colouring matched the clique size is right only when it does match; triangle-free graphs break the habit.
• Confusing covers with colourings. Using c_k as if it were P(G, k) overstates the count, 163,680 against 12,480 for Grötzsch.
• Memory. The i(S) table has 2^n entries; at n = 30 that is about a billion integers. Check n before allocating, and fail fast with a clear message rather than letting the process swap.
• Big-integer time. i(S)^k grows with k, and Python spends most of its time on multiplication. Use modular arithmetic when only positivity matters, and confirm zeros.
• Labelled versus unlabelled. P counts labelled colourings. Dividing by k! counts partitions only for the exact-k terms, not P itself.

What to do next

1. Implement the inclusion-exclusion function and test it against brute force on a few hundred random graphs with up to 7 vertices.
2. Build the Grötzsch graph with Mycielski's construction and reproduce c_3 = 0 and c_4 = 163,680.
3. Add the reduction pipeline: components, blocks, low-degree peeling.
4. Compute ω, ceil(n / α) and DSATUR on your real instance and see whether they already meet.
5. For instances above about 20 vertices that do not close, try a SAT encoding with a time limit, and record the best bounds when it times out.
6. Read the polynomial article to see what extra the full count gives you.