Graph Coloring and Chromatic Polynomials

Graph coloring assigns labels ("colors") to the vertices of a graph so that adjacent vertices receive different colors; the minimum number of colors needed is the chromatic number

χ (G)

. The chromatic polynomial

P (G, k)

counts the number of proper colorings using

k

colors and is a polynomial in

k

. Applies to scheduling, register allocation, frequency assignment, and map coloring. Foundational work by Birkhoff (1912), Whitney (1932), and the Four Color Theorem (Appel–Haken, 1976).

A proper $k$ -coloring of a graph $G = (V, E)$ is a function $c : V \to {1, \dots, k}$ such that $c (u) \neq = c (v)$ whenever $uv \in E$ . The smallest $k$ for which such a coloring exists is the chromatic number $χ (G)$ , a single integer that compactly encodes a deep structural property of the graph. Remarkably, the number of proper $k$ -colorings is always a polynomial in $k$ — a fact discovered by Birkhoff while attacking the Four Color Theorem. The surprising fact: this counting polynomial encodes $χ (G)$ as its smallest positive integer root, and its coefficients alternate in sign and carry combinatorial meaning (subgraph counts). Graph coloring sits at the crossroads of combinatorics, complexity theory (it is NP-hard in general), and applications from compilers to cell-phone networks.

The Core Insight

Two questions live side by side. Existence: how few colors suffice? That's $χ (G)$ . Enumeration: how many ways can we color with $k$ colors? That's $P (G, k)$ . The astonishing bridge between them is deletion–contraction: removing an edge versus merging its endpoints relates the colorings of three graphs by one identity. This single recurrence proves $P (G, k)$ is a polynomial, lets you compute it, and reveals that all coloring information about $G$ is captured by a finite list of integer coefficients.

Formal Statement

Proper Coloring and Chromatic Number

Let $G = (V, E)$ be a finite simple graph with $∣ V ∣ = n$ vertices and $∣ E ∣ = m$ edges.

A proper $k$ -coloring is a map $c : V \to {1, 2, \dots, k}$ with $c (u) \neq = c (v)$ for every edge $uv \in E$ .

The chromatic number is

χ (G) = min {k \in Z_{> 0} : G admits a proper k -coloring} .

⟳well-defined because

k = n

(all distinct colors) always works, so the set is nonempty and bounded below by 1.

A graph is $k$ -colorable if $χ (G) \leq k$ and $k$ -chromatic if $χ (G) = k$ .

Chromatic Polynomial

The chromatic polynomial $P (G, k)$ is the number of proper colorings of $G$ using a palette of $k$ available colors (colors need not all be used). It satisfies

χ (G) = min {k \in Z_{> 0} : P (G, k) > 0} .

⟳

P (G, k) > 0

iff at least one proper

k

-coloring exists, which is the definition of

k

-colorability.

For the empty graph $\overline{K_{n}}$ (no edges) and the complete graph $K_{n}$ :

P (\overline{K_{n}}, k) = k^{n}, P (K_{n}, k) = k (k - 1) (k - 2) \dots (k - n + 1) = k^{\underline{n}} .

⟳with no edges each vertex is free (

k

choices each); for

K_{n}

all vertices mutually adjacent so colors must be distinct — a falling factorial.

Fundamental Properties of $P(G,k)$

For a graph $G$ with $n$ vertices, $m$ edges, and $c$ connected components:

$P (G, k)$ is a polynomial in $k$ of degree exactly $n$ , with leading coefficient $1$ .
The coefficient of $k^{n - 1}$ is $- m$ .
Coefficients alternate in sign: $P (G, k) = \sum_{i = 0}^{n} (- 1)^{n - i} a_{i} k^{i}$ with $a_{i} \geq 0$ .
The constant term is $0$ (i.e. $P (G, 0) = 0$ ); more precisely $k^{c} ∣ P (G, k)$ .
The smallest power of $k$ dividing $P (G, k)$ equals the number of connected components $c$ .

Deletion–Contraction

For any edge $e = uv$ of $G$ , let $G - e$ denote $G$ with $e$ deleted and $G / e$ denote $G$ with $u, v$ identified (contraction, merging parallel edges). Then

P (G, k) = P (G - e, k) - P (G / e, k) .

⟳proper colorings of

G - e

split into those with

c (u) \neq = c (v)

(= colorings of

G

) and those with

c (u) = c (v)

(= colorings of

G / e

Why It Holds / Derivation

Deletion–Contraction and Polynomiality

Step 1 — Partition the colorings of $G - e$ . Take any proper coloring of

G - e

where

e = uv

. In

G - e

the vertices

u, v

are not constrained relative to each other, so two disjoint cases occur:

(A) $c (u) \neq = c (v)$ : this coloring is also proper for $G$ (the only extra edge $e$ is satisfied).
(B) $c (u) = c (v)$ : this coloring corresponds bijectively to a proper coloring of $G / e$ , since identifying $u$ and $v$ into one vertex (which now carries that common color) gives a valid coloring, and conversely.

Step 2 — Count. Case (A) has

P (G, k)

colorings; case (B) has

P (G / e, k)

; together they exhaust

G - e

P (G - e, k) = P (G, k) + P (G / e, k) .

⟳the two cases are mutually exclusive and exhaustive among proper colorings of

G - e

Rearranging gives equation [4].

Step 3 — Polynomiality by induction on $m$ . Base case

m = 0

G = \overline{K_{n}}

with

P = k^{n}

, a polynomial. Inductive step: any graph with

m \geq 1

edges has both

G - e

(with

m - 1

edges) and

G / e

(with

< n

vertices and

\leq m - 1

edges) of strictly smaller edge count. By induction both are polynomials in

k

, hence so is their difference.

■

Step 4 — Degree and leading terms.

G - e

has

n

vertices,

G / e

has

n - 1

. By induction

P (G - e, k) = k^{n} - (m - 1) k^{n - 1} + \dots

and

P (G / e, k) = k^{n - 1} + \dots

. Subtracting:

P (G, k) = k^{n} - (m - 1) k^{n - 1} - k^{n - 1} + \dots = k^{n} - m k^{n - 1} + \dots

⟳track only the top two coefficients through equation [4]; the

k^{n - 1}

terms accumulate

- (m - 1) - 1 = - m

Connected Components Multiply, Constant Term Vanishes

Multiplicativity. If

G

is the disjoint union

G_{1} ⊔ G_{2}

, a proper coloring is an independent choice on each part, so

P (G_{1} ⊔ G_{2}, k) = P (G_{1}, k) \cdot P (G_{2}, k) .

⟳the color of a vertex in

G_{1}

places no constraint on any vertex in

G_{2}

— independent counting.

Constant term. Each connected component contributes a factor with

P (component, 0) = 0

(zero colors color nothing on a nonempty vertex set), and one shows each connected factor is divisible by

k

exactly once when joined; more carefully, a connected graph

H

has

k ∣ P (H, k)

but

k^{2} ∤ P (H, k)

, so

k^{c} ∥ P (G, k)

■

George David Birkhoff | 1884–1944

Birkhoff introduced the chromatic polynomial in 1912 as a strategic detour: rather than prove directly that every planar map needs only four colors, he proposed to count the four-colorings $P (G, 4)$ and show this count is always positive. While the program did not by itself crack the Four Color Theorem, it founded the entire theory of chromatic polynomials. Birkhoff, an American mathematician at Harvard better known for his ergodic theorem in dynamical systems, treated the polynomial's coefficients and roots as objects of independent interest. His student-era collaborator Daniel Lewis and later Hassler Whitney developed the structural and subgraph-counting interpretations. The dream of attacking the four-color problem via the analytic behavior of $P (G, 4)$ persists in modern work on the location of chromatic roots.

Building Intuition

Think of coloring as constraint satisfaction. Each vertex is a slot; each edge is a "must differ" rule. The chromatic number asks: how few categories do I need so that no two things that conflict share a category?

Two extremes anchor your intuition:

No edges → every vertex independent → $k^{n}$ colorings, $χ = 1$ .
All edges (clique $K_{n}$ ) → maximal conflict → $χ = n$ and only the falling factorial $k^{\underline{n}}$ colorings.

A bipartite graph (one with no odd cycle) needs only 2 colors — color the two sides of the partition. So $χ = 2$ exactly when $G$ has at least one edge but no odd cycle. The presence of an odd cycle is the simplest obstruction forcing a third color.

For the polynomial, picture deletion–contraction as a binary tree: each edge you process branches into "keep it (delete)" and "merge it (contract)." The leaves are edgeless graphs whose polynomials are pure powers $k^{n_{i}}$ . Summing the leaves with signs reconstructs $P (G, k)$ — a fully mechanical, if exponential, algorithm.

Deletion–contraction on the triangle $K_3$, yielding $P(K_3,k)=k(k-1)(k-2)$

Worked Examples

Chromatic Polynomial of a Path and a Cycle

Given: the path

P_{n}

(

n

vertices in a line,

n - 1

edges) and the cycle

C_{n}

(

n

vertices in a ring,

n

edges). Path $P_{n}$ . Color vertices left to right. The first vertex has

k

choices; each subsequent vertex must merely differ from its single colored predecessor, giving

k - 1

choices:

P (P_{n}, k) = k (k - 1)^{n - 1} .

⟳greedy left-to-right counting; no later vertex constrains earlier ones, so choices multiply.

So $χ (P_{n}) = 2$ for $n \geq 2$ (it is bipartite).

Cycle $C_{n}$ . Apply deletion–contraction to one edge

e

of the cycle. Then

C_{n} - e = P_{n}

(the cycle opens into a path) and

C_{n} / e = C_{n - 1}

. Thus

P (C_{n}, k) = P (P_{n}, k) - P (C_{n - 1}, k) = k (k - 1)^{n - 1} - P (C_{n - 1}, k) .

⟳deleting one edge of a ring gives a path; contracting it gives a shorter ring.

Solving this recurrence (with $P (C_{3}, k) = k (k - 1) (k - 2)$ ) gives the closed form

P (C_{n}, k) = (k - 1)^{n} + (- 1)^{n} (k - 1) .

⟳the homogeneous solution is

(k - 1)^{n}

; check the base case

n = 3

to fix the

(- 1)^{n} (k - 1)

correction term.

Numerical check, $n = 4$ , $k = 3$ :

P (C_{4}, 3) = (2)^{4} + (- 1)^{4} (2) = 16 + 2 = 18

. Direct count of 3-colorings of a 4-cycle indeed gives

18

P (C_{n}, k) = (k - 1)^{n} + (- 1)^{n} (k - 1), χ (C_{n}) = {23 n even n odd

A Tree and a Concrete Scheduling Count

Given: a company schedules 5 final exams (vertices A,B,C,D,E). Two exams conflict (edge) if some student takes both: pairs

{A, B}, {A, C}, {B, C}, {C, D}, {D, E}

. We have

k = 4

available time slots ("colors"). How many valid timetables exist, and what is the minimum number of slots? Build the graph: edges = AB, AC, BC, CD, DE. Vertices A,B,C form a triangle

K_{3}

; D attaches to C; E attaches to D — a triangle with a pendant path. Decompose. This graph is "

K_{3}

with a path

C - D - E

hanging off." Use the rule for adding a vertex adjacent to exactly one already-colored vertex (it multiplies by

k - 1

P (G, k) = triangle A B C k (k - 1) (k - 2) \cdot D adj to C (k - 1) \cdot E adj to D (k - 1) .

⟳attaching a leaf to an already-colored vertex multiplies the count by

(k - 1)

since the leaf only avoids its one neighbor.

Plug in $k = 4$ :

P (G, 4) = 4 \cdot 3 \cdot 2 \cdot 3 \cdot 3 = 24 \cdot 9 = 216.

Minimum slots: the triangle forces

χ \geq 3

; three slots suffice (color A,B,C distinctly, then D≠C, E≠D), so

χ (G) = 3

P (G, 4) = 216 valid 4-slot timetables; χ (G) = 3 slots minimum

Common Misconceptions

$χ (G)$ is not always equal to the maximum degree plus one. A common error is to assume

χ (G) = Δ (G) + 1

. In fact Brooks' Theorem says

χ (G) \leq Δ (G) + 1

always, with equality only for complete graphs and odd cycles. For most graphs

χ (G)

is strictly smaller. A long even path has

Δ = 2

but

χ = 2

, not

3

. A graph's chromatic polynomial does not determine the graph. Different (non-isomorphic) graphs can share the same chromatic polynomial; they are called chromatically equivalent. So

P (G, k)

is a powerful invariant but not a complete one. Containing a large clique gives only a lower bound. If the largest clique has size

ω (G)

, then

χ (G) \geq ω (G)

, but the gap can be arbitrarily large: there exist triangle-free graphs (

ω = 2

) with arbitrarily large chromatic number (Mycielski's construction). Claim (false): "If

G

has no triangle, then

G

is 2-colorable." Refutation: The 5-cycle $C_{5}$ has no triangle (its shortest cycle has length 5) yet

χ (C_{5}) = 3

. By equation [10],

P (C_{5}, 2) = (1)^{5} + (- 1)^{5} (1) = 1 - 1 = 0

, confirming no proper 2-coloring exists, while

P (C_{5}, 3) = 2^{5} - 2 = 30 > 0

. More dramatically, the Grötzsch graph is triangle-free with

χ = 4

, and Mycielski's iteration produces triangle-free graphs of every chromatic number. Absence of triangles bounds neither

χ

from above nor near 2.

Connections

Graph coloring threads through much of discrete mathematics:

Bipartite Graphs: exactly the 2-colorable graphs; equivalently, graphs with no odd cycle (König's characterization).
Chromatic Number and Independent Sets: a color class is an independent set, so a $k$ -coloring is a partition of $V$ into $k$ independent sets. Thus $χ (G)$ is the minimum number of independent sets covering $V$ .
The Tutte Polynomial: $P (G, k)$ is a specialization $P (G, k) = (- 1)^{n - c} k^{c} T (G; 1 - k, 0)$ of the two-variable Tutte polynomial, linking coloring to flows and the structure of matroids.
Planar Graphs and the Four Color Theorem: every planar graph is 4-colorable, the celebrated and computer-aided result.
Computational Complexity and NP-Completeness: deciding whether $χ (G) \leq 3$ is NP-complete, placing exact coloring among the hardest tractable-to-state problems.
Edge Coloring and Vizing's Theorem: the dual notion coloring edges so no two sharing a vertex match; $χ^{'} (G) \in {Δ, Δ + 1}$ .

Real-World Applications

Register allocation in compilers (e.g., GCC, LLVM): variables alive simultaneously interfere (edge); registers are colors; minimizing registers used is a graph-coloring problem solved via Chaitin's algorithm.
Radio/cellular frequency assignment: transmitters that would interfere are adjacent; assigning non-conflicting frequency channels is a coloring (often a generalization, $T$ -coloring or list-coloring).
Exam and course timetabling: as in the worked example — conflicting events become adjacent vertices, time slots become colors; $χ$ is the minimum number of periods.
Sudoku and constraint puzzles: a completed Sudoku is a proper 9-coloring of a specific 81-vertex graph whose edges encode row, column, and box constraints.
Map coloring / GIS cartography: adjacent regions need different shades; planar duality gives a graph whose 4-colorability is guaranteed by the Four Color Theorem.
Sparse matrix computation: coloring the column-intersection graph lets a numerical solver evaluate many Jacobian entries simultaneously, accelerating finite-difference derivatives.
Aircraft / bandwidth scheduling and CPU task assignment: mutually exclusive resource demands form a conflict graph; coloring partitions tasks into non-conflicting batches.

Historical Development

1852 — Francis Guthrie poses the Four Color Conjecture while coloring a map of England's counties; passed via De Morgan to the mathematical community.
1879 — Alfred Kempe publishes a "proof" of the Four Color Theorem using "Kempe chains"; widely accepted for a decade.
1890 — Percy Heawood finds the flaw in Kempe's argument but salvages it to prove the Five Color Theorem and establishes the Heawood bound for higher-genus surfaces.
1912 — G. D. Birkhoff introduces the chromatic polynomial $P (G, k)$ , hoping to prove the Four Color Theorem by showing $P (G, 4) > 0$ for planar graphs.
1932 — Hassler Whitney develops broken-circuit theory, giving combinatorial meaning to the coefficients of $P (G, k)$ via subgraph counts.
1941 — R. L. Brooks proves Brooks' Theorem: $χ (G) \leq Δ (G) + 1$ , with equality only for cliques and odd cycles.
1955 — Jan Mycielski constructs triangle-free graphs with arbitrarily large chromatic number, shattering naive clique-based intuition.
1968 — Tutte (and earlier Whitney) clarify the connection between chromatic and flow polynomials, unified by the Tutte polynomial.
1976 — Kenneth Appel and Wolfgang Haken prove the Four Color Theorem with extensive computer assistance — the first major theorem to rely on a computer.

Subtleties & Limits

Where can the roots of $P (G, k)$ live? The real and complex zeros of chromatic polynomials ("chromatic roots") are far from understood. Key facts and open questions:

No chromatic root lies in the intervals $(- \infty, 0)$ , $(0, 1)$ , or $(1, 32/27]$ — proven by Jackson and Thomassen for connected graphs.
It is a theorem (Tutte) that $P (G, k)$ has no roots in $(1, 32/27]$ , but the distribution of complex roots is largely conjectural; they are dense in the complex plane for general graphs (Sokal, 2004).
Birkhoff–Lewis conjecture: for planar graphs, $P (G, k) > 0$ for all real $k \geq 5$ (known for $k = 5$ and large $k$ , open in between historically; resolved positively in key cases but the full real-line behavior remains delicate).
Hadwiger's Conjecture (1943), among the deepest open problems in the field, asserts every graph with $χ (G) \geq t$ contains $K_{t}$ as a minor — proven for $t \leq 6$ , open for $t \geq 7$ .
Computational reality: evaluating $P (G, k)$ exactly is #P-hard, and even deciding $χ (G) \leq 3$ is NP-complete, so the elegant theory coexists with intrinsic computational intractability.