Graph colouring and chromatic polynomials

A proper colouring of a graph assigns a colour to each vertex so that adjacent vertices receive different colours. The chromatic number \(\chi(G)\) is the fewest colours that suffice. Colouring 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\)-colourable if it has a proper colouring with \(k\) colours; equivalently, its vertices split into \(k\) independent sets, the colour 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-colourability: deciding whether \(\chi(G) \le 3\) is NP-complete.

Lower bounds. If \(G\) contains a clique of size \(\omega(G)\), those vertices need distinct colours, so \(\chi(G) \ge \omega(G)\). Each colour 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 colouring). 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 neighbours. A vertex has at most \(\Delta\) neighbours, so at most \(\Delta\) colours 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\) colours. Conversely, for every graph some order makes greedy optimal: list the vertices class by class according to an optimal colouring. 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 colours. 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 neighbour, so at most \(\Delta - 1\) earlier ones. If the graph is \(\Delta\)-regular, Brooks finds a vertex \(v\) with two nonadjacent neighbours \(x\) and \(y\) such that removing \(x\) and \(y\) leaves the graph connected; colouring \(x\) and \(y\) first with the same colour and \(v\) last ensures \(v\) sees at most \(\Delta - 1\) distinct colours. 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 neighbour 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 colouring is a global property that local structure cannot detect.

Colouring planar graphs

In October 1852 Francis Guthrie, colouring a map of the counties of England, noticed that four colours 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-colourable?

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

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

Proof. Induct on \(n\). Choose a vertex \(v\) of degree at most 5 and 5-colour \(G - v\). If the neighbours of \(v\) use at most four colours, a fifth is free for \(v\). Otherwise \(v\) has five neighbours \(v_1, \ldots, v_5\) in clockwise order around \(v\), with colours \(1, \ldots, 5\). Consider the subgraph \(H_{13}\) of vertices coloured 1 or 3. If \(v_1\) and \(v_3\) lie in different components of \(H_{13}\), swap colours 1 and 3 in the component containing \(v_1\); the colouring stays proper, \(v_1\) becomes colour 3, and colour 1 is free for \(v\). Otherwise there is a path from \(v_1\) to \(v_3\) using only colours 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 coloured 1 or 3. Swap colours 2 and 4 in the component containing \(v_2\), and colour \(v\) with 2. These two-coloured components are called Kempe chains, after Kempe, whose flawed four colour argument contained this idea.

The four colour theorem. Kenneth Appel and Wolfgang Haken proved in 1976 that every planar graph is 4-colourable. 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 colours.

Edge colouring

An edge colouring gives adjacent edges, those sharing an endpoint, different colours. 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 colouring of \(K_{2m}\) with \(2m - 1\) colours. The Petersen graph has \(\Delta = 3\) but \(\chi' = 4\).

The chromatic polynomial

George Birkhoff introduced in 1912, in an attempt on the four colour problem, the function \(P(G, k)\) giving the number of proper colourings of \(G\) using colours 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\), colour the vertices one at a time: \(P(K_n, k) = k(k - 1)\cdots(k - n + 1)\). For a tree on \(n\) vertices, colour 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 colourings of \(G - e\) are of two kinds: those giving \(u\) and \(v\) different colours, which are exactly the proper colourings of \(G\), and those giving them the same colour, which correspond exactly to proper colourings 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}\) colourings. 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 colour 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-colourings, and whose value at \(-1\) counts acyclic orientations.