Chapter 69. Chromatic Polynomial

The chromatic number records the least number of colors needed to color a graph. The chromatic polynomial records more information. It counts how many proper colorings are possible when a fixed number of colors is available.

For a graph $G$ , the chromatic polynomial is usually written

P_G(k)

\chi_G(k).

In this chapter, we write $P_G(k)$ to avoid confusion with the chromatic number $\chi(G)$ .

69.1 Definition

Let $G=(V,E)$ be a finite graph. For a positive integer $k$ , let $P_G(k)$ denote the number of proper vertex colorings of $G$ using colors from the set

\{1,2,\ldots,k\}.

Thus $P_G(k)$ counts all functions

c:V\to \{1,2,\ldots,k\}

such that

uv\in E \quad \Longrightarrow \quad c(u)\ne c(v).

The surprising fact is that this counting function is always a polynomial in $k$ . This polynomial is called the chromatic polynomial of $G$ . The deletion-contraction identity is one standard way to prove polynomiality.

69.2 First Examples

Let $N_n$ be the graph with $n$ vertices and no edges. Since there are no adjacency restrictions, each vertex may receive any of the $k$ colors. Therefore

P_{N_n}(k)=k^n.

For the complete graph $K_n$ , all vertices must receive distinct colors. The first vertex has $k$ choices, the second has $k-1$ , and so on. Hence

P_{K_n}(k)=k(k-1)(k-2)\cdots(k-n+1).

For the path $P_n$ with $n\ge 1$ , the first vertex has $k$ choices. Each later vertex must avoid the color of the previous vertex, so it has $k-1$ choices. Thus

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

For a tree $T$ with $n$ vertices, the same formula holds:

P_T(k)=k(k-1)^{n-1}.

A tree has no cycles, so after choosing a root, each non-root vertex only needs to avoid the color of its parent.

69.3 Relation to Chromatic Number

The chromatic polynomial determines the chromatic number.

A graph is $k$ -colorable exactly when

P_G(k)>0.

Therefore

\chi(G)=\min\{k\ge 1:P_G(k)>0\}.

The chromatic number gives the first positive integer at which the chromatic polynomial becomes positive.

For example, if

P_G(1)=0,\qquad P_G(2)=0,\qquad P_G(3)>0,

then

\chi(G)=3.

Thus the chromatic polynomial refines the chromatic number. It does not merely say whether a coloring exists. It counts how many colorings exist for every allowed number of colors.

69.4 Deletion and Contraction

The most important recursive method for chromatic polynomials uses deletion and contraction.

Let $e=uv$ be an edge of $G$ .

The deletion $G-e$ is the graph obtained by removing the edge $e$ while keeping all vertices.

The contraction $G/e$ is the graph obtained by identifying $u$ and $v$ as a single vertex and then removing the edge $e$ . In simple graphs, parallel edges created by contraction may be replaced by a single edge.

Deletion removes a constraint. Contraction identifies the two endpoints of that constraint.

These two operations are related because every proper coloring of $G-e$ falls into one of two classes:

Case	Meaning
$u$ and $v$ have different colors	The coloring is a proper coloring of $G$
$u$ and $v$ have the same color	The coloring corresponds to a coloring of $G/e$

This gives the deletion-contraction formula:

P_G(k)=P_{G-e}(k)-P_{G/e}(k).

This identity is the standard recursive formula for the chromatic polynomial. It follows by subtracting the colorings of $G-e$ in which the endpoints of $e$ receive the same color.

69.5 Base Cases

The deletion-contraction formula reduces the number of edges. Repeated use eventually reaches graphs with no edges, whose chromatic polynomials are known.

If $G$ has $n$ vertices and no edges, then

P_G(k)=k^n.

If $G$ has a loop, then

P_G(k)=0.

A loop joins a vertex to itself. Proper coloring would require a vertex to have a color different from itself, which is impossible.

These two base cases allow recursive computation.

69.6 Example: A Triangle

Let $G=K_3$ . Choose an edge $e$ . Then $G-e$ is a path on three vertices, and $G/e$ is $K_2$ .

Thus

P_{K_3}(k)=P_{P_3}(k)-P_{K_2}(k).

We know

P_{P_3}(k)=k(k-1)^2

and

P_{K_2}(k)=k(k-1).

Therefore

P_{K_3}(k)=k(k-1)^2-k(k-1).

Factor:

P_{K_3}(k)=k(k-1)\bigl((k-1)-1\bigr).

Hence

P_{K_3}(k)=k(k-1)(k-2).

This agrees with the direct count for a complete graph on three vertices.

69.7 Example: A Cycle

Let $C_n$ be a cycle with $n\ge 3$ vertices. Its chromatic polynomial is

P_{C_n}(k)=(k-1)^n+(-1)^n(k-1).

This formula explains the parity behavior of cycles.

For an even cycle,

P_{C_n}(2)=1^n+1=2.

There are exactly two proper 2-colorings, corresponding to the two choices of color for the first vertex.

For an odd cycle,

P_{C_n}(2)=1^n-1=0.

Thus an odd cycle is not 2-colorable.

69.8 Basic Properties

Let $G$ be a graph with $n$ vertices, $m$ edges, and $c$ connected components.

The chromatic polynomial has several important structural properties:

Property	Statement
Degree	$P_G(k)$ has degree $n$
Leading coefficient	The leading coefficient is $1$
Second coefficient	The coefficient of $k^{n-1}$ is $-m$
Constant term	If $n>0$ , then $P_G(0)=0$
Lowest nonzero degree	The lowest nonzero power is $k^c$

The degree and leading coefficient follow from the fact that, without edge restrictions, there would be $k^n$ colorings. Edges remove some assignments, but they do not change the leading term.

The coefficient of $k^{n-1}$ records the number of edges with a negative sign. These facts are standard consequences of deletion-contraction and induction on the number of edges.

69.9 Disconnected Graphs

If a graph is the disjoint union of components

G_1,G_2,\ldots,G_r,

then colorings of the components may be chosen independently.

Therefore

P_G(k)=P_{G_1}(k)P_{G_2}(k)\cdots P_{G_r}(k).

For example, if $G$ is the disjoint union of a triangle and an isolated vertex, then

P_G(k)=P_{K_3}(k)\cdot k.

Thus

P_G(k)=k^2(k-1)(k-2).

Independence of components turns the chromatic polynomial into a product.

69.10 Complete Bipartite Examples

Consider the complete bipartite graph $K_{1,n}$ , also called a star. The center has $k$ choices. Each leaf must avoid the color of the center, but leaves are mutually nonadjacent. Hence

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

More generally, complete bipartite graphs $K_{m,n}$ have more complicated chromatic polynomials. One can compute them by first choosing the set of colors used on one part, then assigning colors to the other part while avoiding those colors.

This illustrates a common theme: symmetry can simplify counting, but dense adjacency between parts still creates nontrivial combinatorics.

69.11 Roots of the Chromatic Polynomial

A number $\lambda$ is called a chromatic root of $G$ if

P_G(\lambda)=0.

All nonnegative integers smaller than $\chi(G)$ are chromatic roots. For example, if $\chi(G)=4$ , then

P_G(0)=P_G(1)=P_G(2)=P_G(3)=0.

Chromatic roots are also studied over the real and complex numbers. Their behavior is subtle and connects graph coloring with algebra, statistical physics, and the Tutte polynomial.

For elementary graph theory, the most important roots are the integer roots, since they indicate impossible numbers of colors.

69.12 Chromatic Equivalence

Two graphs $G$ and $H$ are chromatically equivalent if

P_G(k)=P_H(k).

Chromatically equivalent graphs need not be isomorphic. The chromatic polynomial records important information, but it does not determine the graph completely.

A graph is chromatically unique if every graph with the same chromatic polynomial is isomorphic to it.

Thus chromatic polynomials give a graph invariant, but not a complete invariant.

69.13 Connection with the Tutte Polynomial

The chromatic polynomial is a specialization of the Tutte polynomial.

The Tutte polynomial is a two-variable graph polynomial that unifies many graph invariants, including the chromatic polynomial, flow polynomial, and number of spanning trees. Deletion-contraction is one of its central principles.

This connection places graph coloring inside a broader algebraic framework.

In advanced graph theory, the chromatic polynomial is often studied as part of this larger family of deletion-contraction invariants.

69.14 Computational Aspects

Deletion-contraction gives a conceptually simple algorithm, but it may be computationally expensive.

Each edge creates two recursive branches:

G-e

and

G/e.

Thus a naive implementation may require exponentially many steps.

For special graph classes, faster methods exist. Trees, cycles, complete graphs, and certain decomposable graphs have closed formulas. More generally, algorithms exploit structure such as low treewidth, cut vertices, separations, or chordality.

Computing chromatic polynomials belongs to the broader study of graph counting problems, many of which are computationally hard.

69.15 Summary

The chromatic polynomial $P_G(k)$ counts proper $k$ -colorings of a graph.

It refines the chromatic number by recording not only whether a coloring exists, but how many such colorings exist.

The main ideas are:

Concept	Meaning
$P_G(k)$	Number of proper $k$ -colorings
Chromatic number	First positive integer $k$ with $P_G(k)>0$
Deletion	Remove an edge
Contraction	Identify the endpoints of an edge
Deletion-contraction	$P_G(k)=P_{G-e}(k)-P_{G/e}(k)$
Chromatic root	Root of $P_G(k)$
Chromatic equivalence	Same chromatic polynomial

The chromatic polynomial is one of the first examples of a graph polynomial. It connects coloring, recursion, algebraic invariants, and enumerative combinatorics.

69.16 Exercises

Compute the chromatic polynomial of $K_2$ .
Compute the chromatic polynomial of $P_4$ .
Compute the chromatic polynomial of $K_4$ .
Prove that if $G$ has no edges and $n$ vertices, then $P_G(k)=k^n$ .
Prove that if $G$ has a loop, then $P_G(k)=0$ .
Use deletion-contraction to compute the chromatic polynomial of $C_4$ .
Verify that

P_{C_n}(k)=(k-1)^n+(-1)^n(k-1)

for $n=3$ and $n=4$ .

Prove that if $G$ is the disjoint union of $G_1$ and $G_2$ , then

P_G(k)=P_{G_1}(k)P_{G_2}(k).

Show that the coefficient of $k^{n-1}$ in $P_G(k)$ is $-|E(G)|$ .
Give two non-isomorphic graphs with the same chromatic polynomial.
Prove that $P_G(k)>0$ if and only if $G$ is $k$ -colorable.
Compute the chromatic polynomial of the star $K_{1,n}$ .
Explain why the chromatic polynomial is a graph invariant.
Use deletion-contraction to show that $P_G(k)$ is a polynomial in $k$ .
Find the chromatic roots of $K_3$ .