Graph coloring and chromatic polynomials

A proper coloring of a graph assigns a color to each vertex so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the fewest colors that suffice. Coloring models every situation in which conflicting items must be separated: exams that share students must be in different time slots, radio transmitters that are close must use different frequencies, and variables that are live at the same time in a program must sit in different processor registers. The subject began with a question about maps in 1852 and grew into one of the central topics of graph theory.

Basic facts and bounds

A graph is \(k\)-colorable if it has a proper coloring with \(k\) colors; equivalently, its vertices split into \(k\) independent sets, the color classes. Some values: \(\chi(K_n) = n\); \(\chi(C_n) = 2\) for even \(n\) and 3 for odd \(n\); a graph with at least one edge has \(\chi = 2\) exactly when it is bipartite, which by the theorem proved in MATH-260 means it has no odd cycle. There is no comparably simple test for 3-colorability: deciding whether \(\chi(G) \le 3\) is NP-complete.

Lower bounds. If \(G\) contains a clique of size \(\omega(G)\), those vertices need distinct colors, so \(\chi(G) \ge \omega(G)\). Each color class is independent, so if \(\alpha(G)\) is the largest size of an independent set, \(\chi(G) \ge n/\alpha(G)\). Neither bound is close to tight in general.

Theorem (greedy coloring). For every graph, \(\chi(G) \le \Delta(G) + 1\).

Proof. List the vertices in any order and give each the smallest positive integer not already used by one of its earlier neighbors. A vertex has at most \(\Delta\) neighbors, so at most \(\Delta\) colors are forbidden when it is reached, and one of \(1, \ldots, \Delta + 1\) is free.

The greedy algorithm is sensitive to the order. In the crown graph, two rows \(a_1, \ldots, a_m\) and \(b_1, \ldots, b_m\) with \(a_i\) joined to \(b_j\) whenever \(i \ne j\), the graph is bipartite, but the order \(a_1, b_1, a_2, b_2, \ldots\) makes greedy use \(m\) colors. Conversely, for every graph some order makes greedy optimal: list the vertices class by class according to an optimal coloring. A useful heuristic, due to Welsh and Powell in 1967, processes vertices in decreasing order of degree, and gives \(\chi(G) \le \max_i \min(d_i + 1, i)\) when the degrees are sorted \(d_1 \ge d_2 \ge \cdots\).

Theorem (Brooks, 1941). If \(G\) is connected and is neither a complete graph nor an odd cycle, then \(\chi(G) \le \Delta(G)\).

Proof idea. The difficulty is the last vertex in a greedy order, which may see \(\Delta\) different colors. If some vertex has degree less than \(\Delta\), order the vertices so that it comes last, for example in decreasing distance from it; then every other vertex has a later neighbor, so at most \(\Delta - 1\) earlier ones. If the graph is \(\Delta\)-regular, Brooks finds a vertex \(v\) with two nonadjacent neighbors \(x\) and \(y\) such that removing \(x\) and \(y\) leaves the graph connected; coloring \(x\) and \(y\) first with the same color and \(v\) last ensures \(v\) sees at most \(\Delta - 1\) distinct colors. Leonard Brooks proved the theorem as a student at Cambridge, where he was one of the four authors who wrote together under the name Blanche Descartes.

Large chromatic number without triangles. Can \(\chi\) be large merely because of many large cliques? No. Jan Mycielski showed in 1955 how to build triangle-free graphs with any chromatic number. From a graph \(G\) on \(v_1, \ldots, v_n\), add new vertices \(u_1, \ldots, u_n\), with \(u_i\) joined to every neighbor of \(v_i\), and one more vertex \(w\) joined to all the \(u_i\). The new graph is triangle-free if \(G\) is, and its chromatic number is \(\chi(G) + 1\). Starting from a single edge gives \(C_5\) (with \(\chi = 3\)), then the Grötzsch graph with 11 vertices and \(\chi = 4\). Paul Erdős proved in 1959, using the probabilistic method of lesson 12, that there are graphs with no short cycles at all and arbitrarily large chromatic number, so coloring is a global property that local structure cannot detect.

Coloring planar graphs

In October 1852 Francis Guthrie, coloring a map of the counties of England, noticed that four colors sufficed and asked whether this was always true for maps in which countries are connected regions and countries sharing a border must differ. His brother Frederick passed the question to Augustus De Morgan. Arthur Cayley publicized it in 1878, and in 1879 Alfred Kempe published a proof that stood for eleven years until Percy Heawood found a flaw in 1890. Taking the dual graph, the question becomes: is every planar graph 4-colorable?

Theorem (six colors). Every planar graph is 6-colorable. Proof: by induction on \(n\). Lesson 8 showed that a planar graph has a vertex \(v\) of degree at most 5. Color \(G - v\) with six colors by induction; \(v\) has at most five neighbors, so a sixth color is free for it.

Theorem (Heawood, 1890). Every planar graph is 5-colorable.

Proof. Induct on \(n\). Choose a vertex \(v\) of degree at most 5 and 5-color \(G - v\). If the neighbors of \(v\) use at most four colors, a fifth is free for \(v\). Otherwise \(v\) has five neighbors \(v_1, \ldots, v_5\) in clockwise order around \(v\), with colors \(1, \ldots, 5\). Consider the subgraph \(H_{13}\) of vertices colored 1 or 3. If \(v_1\) and \(v_3\) lie in different components of \(H_{13}\), swap colors 1 and 3 in the component containing \(v_1\); the coloring stays proper, \(v_1\) becomes color 3, and color 1 is free for \(v\). Otherwise there is a path from \(v_1\) to \(v_3\) using only colors 1 and 3, and together with \(v\) it forms a cycle that separates \(v_2\) from \(v_4\) in the plane, by the Jordan curve theorem. Then \(v_2\) and \(v_4\) lie in different components of \(H_{24}\), since any path between them would have to cross the cycle at a vertex, which would be colored 1 or 3. Swap colors 2 and 4 in the component containing \(v_2\), and color \(v\) with 2. These two-colored components are called Kempe chains, after Kempe, whose flawed four color argument contained this idea.

The four color theorem. Kenneth Appel and Wolfgang Haken proved in 1976 that every planar graph is 4-colorable. Their proof showed that every planar triangulation contains one of an unavoidable set of 1,936 configurations, later reduced to 1,476, and that each configuration is reducible, meaning it cannot occur in a smallest counterexample; checking reducibility took about 1,200 hours of computer time. Many mathematicians were uneasy about a proof that could not be checked by hand. In 1997 Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas gave a simpler computer proof with 633 configurations, and in 2005 Georges Gonthier verified the whole proof in the Coq proof assistant, removing reasonable doubt. Four is best possible: \(K_4\) is planar and needs four colors.

Edge coloring

An edge coloring gives adjacent edges, those sharing an endpoint, different colors. The edge chromatic number \(\chi'(G)\) is at least \(\Delta(G)\), since the edges at a vertex of maximum degree all differ. Vadim Vizing proved in 1964 that \(\chi'(G)\) is always \(\Delta\) or \(\Delta + 1\). Dénes König proved in 1916 that bipartite graphs always achieve \(\chi' = \Delta\), a fact that follows from the matching theory of lesson 10. Scheduling a round-robin tournament on \(2m\) teams in \(2m - 1\) rounds is exactly an edge coloring of \(K_{2m}\) with \(2m - 1\) colors. The Petersen graph has \(\Delta = 3\) but \(\chi' = 4\).

The chromatic polynomial

George Birkhoff introduced in 1912, in an attempt on the four color problem, the function \(P(G, k)\) giving the number of proper colorings of \(G\) using colors from a set of \(k\). Then \(\chi(G)\) is the smallest positive integer \(k\) with \(P(G, k) > 0\). Some cases are easy. For the empty graph on \(n\) vertices, \(P = k^n\). For \(K_n\), color the vertices one at a time: \(P(K_n, k) = k(k - 1)\cdots(k - n + 1)\). For a tree on \(n\) vertices, color a root in \(k\) ways and then each other vertex differently from its parent: \(P = k(k - 1)^{n-1}\).

Theorem (deletion–contraction). For any edge \(e = uv\) of \(G\), \[P(G, k) = P(G - e, k) - P(G / e, k),\] where \(G - e\) deletes the edge and \(G / e\) contracts it, merging \(u\) and \(v\) into one vertex and removing any resulting multiple edges.

Proof. Proper colorings of \(G - e\) are of two kinds: those giving \(u\) and \(v\) different colors, which are exactly the proper colorings of \(G\), and those giving them the same color, which correspond exactly to proper colorings of \(G / e\). So \(P(G - e, k) = P(G, k) + P(G / e, k)\).

Example: cycles. Applying the theorem to an edge of \(C_n\) gives \(P(C_n) = P(P_n) - P(C_{n-1})\), where \(P_n\) is a path, a tree, with \(k(k - 1)^{n-1}\) colorings. Induction from \(P(C_3) = k(k - 1)(k - 2)\) yields \[P(C_n, k) = (k - 1)^n + (-1)^n(k - 1).\] For \(n = 4\), \((k - 1)^4 + (k - 1) = k(k - 1)^3 - k(k - 1)(k - 2)\), as in the figure. Setting \(k = 2\) gives 2 for even \(n\) and 0 for odd \(n\), as it should.

Properties. Induction with deletion–contraction shows that \(P(G, k)\) is a polynomial in \(k\) of degree \(n\), with leading coefficient 1, coefficient of \(k^{n-1}\) equal to \(-|E|\), integer coefficients alternating in sign, and no constant term. The polynomial also counts something at negative integers: Richard Stanley showed in 1973 that \((-1)^nP(G, -1)\) is the number of acyclic orientations of \(G\). Birkhoff and Lewis conjectured in 1946 that planar graphs have no real chromatic roots at or beyond 4, which would imply the four color theorem; it remains open. In 2012 June Huh proved Read's conjecture of 1968 that the absolute values of the coefficients form a log-concave sequence, work that contributed to his Fields Medal in 2022.

from itertools import product
from functools import lru_cache

def make(edges):
    adj = {}
    for a, b in edges:
        adj.setdefault(a, set()).add(b); adj.setdefault(b, set()).add(a)
    return adj

def greedy(adj, order):
    paint = {}
    for v in order:
        used = {paint[w] for w in adj[v] if w in paint}
        paint[v] = next(c for c in range(len(adj) + 1) if c not in used)
    return paint

def chromatic_number(adj):
    vs = sorted(adj)
    for k in range(1, len(vs) + 1):
        def place(i, paint):
            if i == len(vs):
                return True
            v = vs[i]
            for c in range(k):
                if all(paint.get(w) != c for w in adj[v]):
                    paint[v] = c
                    if place(i + 1, paint):
                        return True
                    del paint[v]
            return False
        if place(0, {}):
            return k

m = 5
crown = make([(("a", i), ("b", j)) for i in range(m) for j in range(m) if i != j])
bad_order = [x for i in range(m) for x in (("a", i), ("b", i))]
good_order = [("a", i) for i in range(m)] + [("b", i) for i in range(m)]
print("crown graph, greedy classes: bad order", len(set(greedy(crown, bad_order).values())),
      " good order", len(set(greedy(crown, good_order).values())))

petersen_edges = [(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
petersen = make(petersen_edges)
print("Petersen: chromatic number", chromatic_number(petersen), " max degree", max(len(s) for s in petersen.values()))

def mycielski(adj):
    n = len(adj)
    idx = {v: i for i, v in enumerate(sorted(adj))}
    edges = [(idx[a], idx[b]) for a in adj for b in adj[a] if idx[a] < idx[b]]
    new = list(edges)
    for a, b in edges:
        new += [(a, n + b), (b, n + a)]
    new += [(n + i, 2 * n) for i in range(n)]
    return make(new)

def has_triangle(adj):
    return any(adj[a] & adj[b] for a in adj for b in adj[a])

g = make([(0, 1)])
for step in range(3):
    print(f"Mycielski step {step}: {len(g)} vertices, triangle-free {not has_triangle(g)}, chromatic number {chromatic_number(g)}")
    g = mycielski(g)

def poly_mul(p, q):
    out = [0] * (len(p) + len(q) - 1)
    for i, a in enumerate(p):
        for j, b in enumerate(q):
            out[i + j] += a * b
    return out

def poly_sub(p, q):
    n = max(len(p), len(q))
    p = p + [0] * (n - len(p)); q = q + [0] * (n - len(q))
    return [a - b for a, b in zip(p, q)]

@lru_cache(maxsize=None)
def chrom_poly(n, edges):
    """Coefficient list (constant term first) by deletion-contraction; vertices 0..n-1."""
    if not edges:
        return tuple([0] * n + [1])
    (u, v), rest = edges[0], edges[1:]
    deleted = chrom_poly(n, rest)
    relabel = lambda x: u if x == v else (x - 1 if x > v else x)
    merged = set()
    for a, b in rest:
        a, b = relabel(a), relabel(b)
        if a != b:
            merged.add((min(a, b), max(a, b)))
    contracted = chrom_poly(n - 1, tuple(sorted(merged)))
    return tuple(poly_sub(list(deleted), list(contracted)))

def evaluate(p, k):
    return sum(c * k ** i for i, c in enumerate(p))

def show(p):
    terms = [f"{c:+d}k^{i}" for i, c in reversed(list(enumerate(p))) if c]
    return " ".join(terms)

for n in [3, 4, 5, 6]:
    cyc = tuple(sorted((i, (i + 1) % n) if i < (i + 1) % n else ((i + 1) % n, i) for i in range(n)))
    p = chrom_poly(n, cyc)
    print(f"C_{n}: {show(p)}   check (k-1)^n + (-1)^n (k-1) at k=5:", evaluate(p, 5), (4) ** n + (-1) ** n * 4)

P = chrom_poly(10, tuple(sorted((min(a, b), max(a, b)) for a, b in petersen_edges)))
print("Petersen chromatic polynomial:", show(P))
print("P(2), P(3), P(4):", [evaluate(P, k) for k in (2, 3, 4)], " acyclic orientations (-1)^n P(-1):", evaluate(P, -1))
brute3 = sum(all(c[a] != c[b] for a, b in petersen_edges) for c in product(range(3), repeat=10))
print("brute-force proper 3-assignments of Petersen:", brute3)

crown graph, greedy classes: bad order 5  good order 2
Petersen: chromatic number 3  max degree 3
Mycielski step 0: 2 vertices, triangle-free True, chromatic number 2
Mycielski step 1: 5 vertices, triangle-free True, chromatic number 3
Mycielski step 2: 11 vertices, triangle-free True, chromatic number 4
C_3: +1k^3 -3k^2 +2k^1   check (k-1)^n + (-1)^n (k-1) at k=5: 60 60
C_4: +1k^4 -4k^3 +6k^2 -3k^1   check (k-1)^n + (-1)^n (k-1) at k=5: 260 260
C_5: +1k^5 -5k^4 +10k^3 -10k^2 +4k^1   check (k-1)^n + (-1)^n (k-1) at k=5: 1020 1020
C_6: +1k^6 -6k^5 +15k^4 -20k^3 +15k^2 -5k^1   check (k-1)^n + (-1)^n (k-1) at k=5: 4100 4100
Petersen chromatic polynomial: +1k^10 -15k^9 +105k^8 -455k^7 +1353k^6 -2861k^5 +4275k^4 -4305k^3 +2606k^2 -704k^1
P(2), P(3), P(4): [0, 120, 12960]  acyclic orientations (-1)^n P(-1): 16680
brute-force proper 3-assignments of Petersen: 120

The crown graph shows how badly greedy can do with a poor order and how well with a good one. The Petersen graph has chromatic number 3 and maximum degree 3, consistent with Brooks' theorem. The Mycielski construction raises the chromatic number by one at each step while staying triangle-free. Deletion–contraction reproduces the cycle formula and gives the full chromatic polynomial of the Petersen graph, whose value at 3 matches a brute-force count of 3-colorings, and whose value at \(-1\) counts acyclic orientations.