Graph Coloring and Chromatic Polynomials

⚡ Key Takeaways

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 $\chi(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).

💡 The Core Insight

Two questions live side by side. Existence: how few colors suffice? That's $\chi(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.

DefinitionProper 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

1

\quad \chi(G)=\min\{\,k\in\mathbb{Z}_{>0} : G \text{ admits a proper } k\text{-coloring}\,\}.

Derivation hint: 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 $\chi(G)\le k$ and $k$ -chromatic if $\chi(G)=k$ .

DefinitionChromatic 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

2

\quad \chi(G)=\min\{\,k\in\mathbb{Z}_{>0} : P(G,k)>0\,\}.

Derivation hint: $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$ :

3

\quad P(\overline{K_n},k)=k^{\,n},\qquad P(K_n,k)=k(k-1)(k-2)\cdots(k-n+1)=k^{\underline{n}}.

Derivation hint: 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.

TheoremFundamental Properties of

P(G,k)

For a graph $G$ with $n$ vertices, $m$ edges, and $c$ connected components: 1. $P(G,k)$ is a polynomial in $k$ of degree exactly $n$ , with leading coefficient $1$ . 2. The coefficient of $k^{n-1}$ is $-m$ . 3. Coefficients alternate in sign: $P(G,k)=\sum_{i=0}^{n}(-1)^{n-i}a_i k^i$ with $a_i\ge 0$ . 4. The constant term is $0$ (i.e. $P(G,0)=0$ ); more precisely $k^c \mid P(G,k)$ . 5. The smallest power of $k$ dividing $P(G,k)$ equals the number of connected components $c$ .

TheoremDeletion–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

4

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

Derivation hint: 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$ ).

ProofDeletion–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$ :

5

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

Derivation hint: 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\ge 1$ edges has both $G-e$ (with $m-1$ edges) and $G/e$ (with $<n$ vertices and $\le m-1$ edges) of strictly smaller edge count. By induction both are polynomials in $k$ , hence so is their difference. $\blacksquare$

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}+\cdots$ and $P(G/e,k)=k^{n-1}+\cdots$ . Subtracting:

6

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

Derivation hint: track only the top two coefficients through equation [4]; the $k^{n-1}$ terms accumulate $-(m-1)-1=-m$ .

∎

ProofConnected Components Multiply, Constant Term Vanishes

Multiplicativity. If $G$ is the disjoint union $G_1\sqcup G_2$ , a proper coloring is an independent choice on each part, so

7

\quad P(G_1\sqcup G_2,\,k)=P(G_1,k)\cdot P(G_2,k).

Derivation hint: 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(\text{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\mid P(H,k)$ but $k^2\nmid P(H,k)$ , so $k^c \| P(G,k)$ . $\blacksquare$

∎

mathematician · 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.

🧠 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, $\chi=1$ .
All edges (clique $K_n$ ) → maximal conflict → $\chi=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 $\chi=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.

Figure

Deletion–contraction on the triangle

K_3

, yielding

P(K_3,k)=k(k-1)(k-2)

ExampleChromatic 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:

8

\quad P(P_n,k)=k(k-1)^{\,n-1}.

Derivation hint: greedy left-to-right counting; no later vertex constrains earlier ones, so choices multiply. So $\chi(P_n)=2$ for $n\ge 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

9

\quad P(C_n,k)=P(P_n,k)-P(C_{n-1},k)=k(k-1)^{n-1}-P(C_{n-1},k).

Derivation hint: 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

10

\quad P(C_n,k)=(k-1)^{n}+(-1)^{n}(k-1).

Derivation hint: 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$ .

\boxed{\;P(C_n,k)=(k-1)^n+(-1)^n(k-1),\qquad \chi(C_n)=\begin{cases}2 & n \text{ even}\\ 3 & n \text{ odd}\end{cases}\;}

ExampleA 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$ ):

11

\quad P(G,k)=\underbrace{k(k-1)(k-2)}_{\text{triangle }ABC}\cdot \underbrace{(k-1)}_{D \text{ adj to } C}\cdot \underbrace{(k-1)}_{E \text{ adj to } D}.

Derivation hint: 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 $\chi\ge 3$ ; three slots suffice (color A,B,C distinctly, then D≠C, E≠D), so $\chi(G)=3$ .

\boxed{\;P(G,4)=216 \text{ valid 4-slot timetables};\quad \chi(G)=3 \text{ slots minimum}\;}

⚠️ Common mistake

$\chi(G)$ is not always equal to the maximum degree plus one. A common error is to assume $\chi(G)=\Delta(G)+1$ . In fact Brooks' Theorem says $\chi(G)\le \Delta(G)+1$ always, with equality only for complete graphs and odd cycles. For most graphs $\chi(G)$ is strictly smaller. A long even path has $\Delta=2$ but $\chi=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 $\omega(G)$ , then $\chi(G)\ge \omega(G)$ , but the gap can be arbitrarily large: there exist triangle-free graphs ( $\omega=2$ ) with arbitrarily large chromatic number (Mycielski's construction).

Counterexample

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 $\chi(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 $\chi=4$ , and Mycielski's iteration produces triangle-free graphs of every chromatic number. Absence of triangles bounds neither $\chi$ from above nor near 2.

connection

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 $\chi(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 $\chi(G)\le 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; $\chi'(G)\in\{\Delta,\Delta+1\}$ .

🔬 Where this appears

⏳ History

- 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:

\chi(G)\le\Delta(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.

open-problem

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\ge 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 $\chi(G)\ge t$ contains $K_t$ as a minor — proven for $t\le 6$ , open for $t\ge 7$ .
Computational reality: evaluating $P(G,k)$ exactly is #P-hard, and even deciding $\chi(G)\le 3$ is NP-complete, so the elegant theory coexists with intrinsic computational intractability.

Graph Coloring and Chromatic Polynomials

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also