
The chromatic polynomial is a
graph polynomial studied in
algebraic graph theory, a branch of
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
. It counts the number of
graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
s as a function of the number of colors and was originally defined by
George David Birkhoff
George David Birkhoff (March21, 1884November12, 1944) was one of the top American mathematicians of his generation. He made valuable contributions to the theory of differential equations, dynamical systems, the four-color problem, the three-body ...
to study the
four color problem. It was generalised to the
Tutte polynomial by
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersion (mathematics), immersions, characteristic classes and, ...
and
W. T. Tutte, linking it to the
Potts model
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenom ...
of
statistical physics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. Sometimes called statistical physics or statistical thermodynamics, its applicati ...
.
History
George David Birkhoff
George David Birkhoff (March21, 1884November12, 1944) was one of the top American mathematicians of his generation. He made valuable contributions to the theory of differential equations, dynamical systems, the four-color problem, the three-body ...
introduced the chromatic polynomial in 1912, defining it only for
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, in an attempt to prove the
four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
. If
denotes the number of proper colorings of ''G'' with ''k'' colors then one could establish the four color theorem by showing
for all planar graphs ''G''. In this way he hoped to apply the powerful tools of
analysis
Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
and
algebra
Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...
for studying the roots of polynomials to the combinatorial coloring problem.
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersion (mathematics), immersions, characteristic classes and, ...
generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In 1968,
Ronald C. Read asked which polynomials are the chromatic polynomials of some graph, a question that remains open, and introduced the concept of chromatically equivalent graphs. Today, chromatic polynomials are one of the central objects of
algebraic graph theory.
Definition

For a graph ''G'',
counts the number of its (proper)
vertex ''k''-colorings.
Other commonly used notations include
,
, or
.
There is a unique
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
which evaluated at any integer ''k'' ≥ 0 coincides with
; it is called the chromatic polynomial of ''G''.
For example, to color the
path graph
In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
on 3 vertices with ''k'' colors, one may choose any of the ''k'' colors for the first vertex, any of the
remaining colors for the second vertex, and lastly for the third vertex, any of the
colors that are different from the second vertex's choice.
Therefore,
is the number of ''k''-colorings of
.
For a variable ''x'' (not necessarily integer), we thus have
.
(Colorings which differ only by permuting colors or by
automorphisms of ''G'' are still counted as different.)
Deletion–contraction
The fact that the number of ''k''-colorings is a polynomial in ''k'' follows from a recurrence relation called the
deletion–contraction recurrence or Fundamental Reduction Theorem. It is based on
edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...
: for a pair of vertices
and
the graph
is obtained by merging the two vertices and removing any edges between them.
If
and
are adjacent in ''G'', let
denote the graph obtained by removing the edge
.
Then the numbers of ''k''-colorings of these graphs satisfy:
:
Equivalently, if
and
are not adjacent in ''G'' and
is the graph with the edge
added, then
:
This follows from the observation that every ''k''-coloring of ''G'' either gives different colors to
and
, or the same colors. In the first case this gives a (proper) ''k''-coloring of
, while in the second case it gives a coloring of
.
Conversely, every ''k''-coloring of ''G'' can be uniquely obtained from a ''k''-coloring of
or
(if
and
are not adjacent in ''G'').
The chromatic polynomial can hence be recursively defined as
:
for the edgeless graph on ''n'' vertices, and
:
for a graph ''G'' with an edge
(arbitrarily chosen).
Since the number of ''k''-colorings of the edgeless graph is indeed
, it follows by induction on the number of edges that for all ''G'', the polynomial
coincides with the number of ''k''-colorings at every integer point ''x'' = ''k''. In particular, the chromatic polynomial is the unique
interpolating polynomial of degree at most ''n'' through the points
:
Tutte’s curiosity about which other
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discre ...
s satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the
Tutte polynomial .
Examples
Properties
For fixed ''G'' on ''n'' vertices, the chromatic polynomial
is a
monic polynomial of degree exactly ''n'', with integer coefficients.
The chromatic polynomial includes at least as much information about the colorability of ''G'' as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a zero of the chromatic polynomial,
:
The polynomial evaluated at
, that is
, yields
times the number of
acyclic orientations of ''G''.
The derivative evaluated at 1,
equals the
chromatic invariant up to sign.
If ''G'' has ''n'' vertices and ''c''
components
Component may refer to:
In engineering, science, and technology Generic systems
*System components, an entity with discrete structure, such as an assembly or software module, within a system considered at a particular level of analysis
* Lumped e ...
, then
* The coefficients of
are zeros.
* The coefficients of
are all non-zero and alternate in signs.
* The coefficient of
is 1 (the polynomial is
monic).
* The coefficient of
is
We prove this via induction on the number of edges on a simple graph ''G'' with
vertices and
edges. When
, ''G'' is an empty graph. Hence per definition
. So the coefficient of
is
, which implies the statement is true for an empty graph. When
, as in ''G'' has just a single edge,
. Thus coefficient of
is
. So the statement holds for k = 1. Using
strong induction
Mathematical induction is a method for proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots all hold. This is done by first proving a simple case, then ...
assume the statement is true for
. Let ''G'' have
edges. By the
contraction-deletion principle,
Let
and
Hence
.
Since
is obtained from ''G'' by removal of just one edge ''e'',
, so
and thus the statement is true for ''k''.
* The coefficient of
is
, where
is the number of triangles (3-cycle subgraphs) in
.
* The coefficient of
is
times the number of acyclic orientations that have a unique sink, at a specified, arbitrarily chosen vertex.
* The absolute values of coefficients of every chromatic polynomial form a
log-concave sequence.
*
The last property is generalized by the fact that if ''G'' is a
''k''-clique-sum of
and
(i.e., a graph obtained by gluing the two at a clique on ''k'' vertices, isomorphic to the complete graph
), then
:
A graph ''G'' with ''n'' vertices is a tree if and only if
:
Chromatic equivalence

Two graphs are said to be ''chromatically equivalent'' if they have the same chromatic polynomial. Isomorphic graphs have the same chromatic polynomial, but non-isomorphic graphs can be chromatically equivalent. For example, all trees on ''n'' vertices have the same chromatic polynomial.
In particular,
is the chromatic polynomial of both the
claw graph and the
path graph
In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
on 4 vertices.
A graph is ''chromatically unique'' if it is determined by its chromatic polynomial, up to isomorphism. In other words, ''G'' is chromatically unique, then
would imply that ''G'' and ''H'' are isomorphic.
All
cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s are chromatically unique.
Chromatic roots
A
root
In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
(or ''zero'') of a chromatic polynomial, called a “chromatic root”, is a value ''x'' where
. Chromatic roots have been very well studied, in fact, Birkhoff’s original motivation for defining the chromatic polynomial was to show that for planar graphs,
for ''x'' ≥ 4. This would have established the
four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
.
No graph can be 0-colored, so 0 is always a chromatic root. Only edgeless graphs can be 1-colored, so 1 is a chromatic root of every graph with at least one edge. On the other hand, except for these two points, no graph can have a chromatic root at a real number smaller than or equal to 32/27. A result of Tutte connects the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if
\fr ...
with the study of chromatic roots, showing that chromatic roots exist very close to
:
If
is a planar triangulation of a sphere then
:
While the real line thus has large parts that contain no chromatic roots for any graph, every point in the
complex plane
In mathematics, the complex plane is the plane (geometry), plane formed by the complex numbers, with a Cartesian coordinate system such that the horizontal -axis, called the real axis, is formed by the real numbers, and the vertical -axis, call ...
is arbitrarily close to a chromatic root in the sense that there exists an infinite family of graphs whose chromatic roots are dense in the complex plane.
Colorings using all colors
For a graph ''G'' on ''n'' vertices, let
denote the number of colorings using exactly ''k'' colors ''up to renaming colors'' (so colorings that can be obtained from one another by permuting colors are counted as one; colorings obtained by
automorphisms of ''G'' are still counted separately).
In other words,
counts the number of
partitions of the vertex set into ''k'' (non-empty)
independent sets.
Then
counts the number of colorings using exactly ''k'' colors (with distinguishable colors).
For an integer ''x'', all ''x''-colorings of ''G'' can be uniquely obtained by choosing an integer ''k ≤ x'', choosing ''k'' colors to be used out of ''x'' available, and a coloring using exactly those ''k'' (distinguishable) colors.
Therefore:
:
where
denotes the
falling factorial
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
\begin
(x)_n = x^\underline &= \overbrace^ \\
&= \prod_^n(x-k+1) = \prod_^(x-k) .
\end ...
.
Thus the numbers
are the coefficients of the polynomial
in the basis
of falling factorials.
Let
be the ''k''-th coefficient of
in the standard basis
, that is:
:
Stirling number
In mathematics, Stirling numbers arise in a variety of Analysis (mathematics), analytic and combinatorics, combinatorial problems. They are named after James Stirling (mathematician), James Stirling, who introduced them in a purely algebraic setti ...
s give a
change of basis
In mathematics, an ordered basis of a vector space of finite dimension allows representing uniquely any element of the vector space by a coordinate vector, which is a sequence of scalars called coordinates. If two different bases are conside ...
between the standard basis and the basis of falling factorials.
This implies:
:
and
Categorification
The chromatic polynomial is
categorified by a homology theory closely related to
Khovanov homology
In mathematics, Khovanov homology is an oriented link invariant that arises as the cohomology of a cochain complex. It may be regarded as a categorification of the Jones polynomial.
It was developed in the late 1990s by Mikhail Khovanov.
Overv ...
.
Algorithms
Computational problems associated with the chromatic polynomial include
* finding the chromatic polynomial
of a given graph ''G'';
* evaluating
at a fixed ''x'' for given ''G''.
The first problem is more general because if we knew the coefficients of
we could evaluate it at any point in polynomial time because the degree is ''n''. The difficulty of the second type of problem depends strongly on the value of ''x'' and has been intensively studied in
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
. When ''x'' is a natural number, this problem is normally viewed as computing the number of ''x''-colorings of a given graph. For example, this includes the problem #3-coloring of counting the number of 3-colorings, a canonical problem in the study of complexity of counting, complete for the counting class
#P.
Efficient algorithms
For some basic graph classes, closed formulas for the chromatic polynomial are known. For instance this is true for trees and cliques, as listed in the table above.
Polynomial time algorithms are known for computing the chromatic polynomial for wider classes of graphs, including
chordal graphs and graphs of bounded
clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs.
It is defined as the minimum number of ...
. The latter class includes
cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s and graphs of bounded
tree-width, such as
outerplanar graphs.
Deletion–contraction
The
deletion-contraction recurrence gives a way of computing the chromatic polynomial, called the ''deletion–contraction algorithm''. In the first form (with a minus), the recurrence terminates in a collection of empty graphs. In the second form (with a plus), it terminates in a collection of complete graphs.
This forms the basis of many algorithms for graph coloring. The ChromaticPolynomial function in the Combinatorica package of the computer algebra system
Mathematica
Wolfram (previously known as Mathematica and Wolfram Mathematica) is a software system with built-in libraries for several areas of technical computing that allows machine learning, statistics, symbolic computation, data manipulation, network ...
uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse. The worst case running time of either formula satisfies the same recurrence relation as the
Fibonacci numbers
In mathematics, the Fibonacci sequence is a sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many writers begin the s ...
, so in the worst case, the algorithm runs in time within a polynomial factor of
:
on a graph with ''n'' vertices and ''m'' edges. The analysis can be improved to within a polynomial factor of the number
of
spanning trees of the input graph. In practice,
branch and bound
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution.
It is an algorithm ...
strategies and
graph isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
rejection are employed to avoid some recursive calls, the running time depends on the heuristic used to pick the vertex pair.
Cube method
There is a natural geometric perspective on graph colorings by observing that, as an assignment of natural numbers to each vertex, a graph coloring is a vector in the integer lattice.
Since two vertices
and
being given the same color is equivalent to the
’th and
’th coordinate in the coloring vector being equal, each edge can be associated with a hyperplane of the form
. The collection of such hyperplanes for a given graph is called its graphic
arrangement
In music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orchestr ...
. The proper colorings of a graph are those lattice points which avoid forbidden hyperplanes.
Restricting to a set of
colors, the lattice points are contained in the cube
. In this context the chromatic polynomial counts the number of lattice points in the