George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem.

for all planar graphs G. In this way he hoped to apply the powerful tools of analysis and algebra for studying the roots of polynomials to the combinatorial coloring problem.

Hassler Whitney 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.

[1] Today, chromatic polynomials are one of the central objects of algebraic graph theory.

; it is called the chromatic polynomial of G. For example, to color the path graph

added, then This follows from the observation that every k-coloring of G either gives different colors to

The chromatic polynomial can hence be recursively defined as Since the number of k-colorings of the edgeless graph is indeed

times the number of acyclic orientations of G.[4] The derivative evaluated at 1,

We prove this via induction on the number of edges on a simple graph G with

and thus the statement is true for k. The last property is generalized by the fact that if G is a k-clique-sum of

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.

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

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.

For instance this is true for trees and cliques, as listed in the table above.

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.

The ChromaticPolynomial function in the Combinatorica package of the computer algebra system Mathematica uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse.

[13] The worst case running time of either formula satisfies the same recurrence relation as the Fibonacci numbers, so in the worst case, the algorithm runs in time within a polynomial factor of on a graph with n vertices and m edges.

[15] In practice, branch and bound strategies and graph isomorphism rejection are employed to avoid some recursive calls, the running time depends on the heuristic used to pick the vertex pair.

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.

’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.

The proper colorings of a graph are those lattice points which avoid forbidden hyperplanes.

In this context the chromatic polynomial counts the number of lattice points in the

is #P-hard for all x (including negative integers and even all complex numbers) except for the three “easy points”.

[16] Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood.

, the corresponding decision problem of deciding if a given graph can be k-colored is NP-hard.

Such problems cannot be approximated to any multiplicative factor by a bounded-error probabilistic algorithm unless NP = RP, because any multiplicative approximation would distinguish the values 0 and 1, effectively solving the decision version in bounded-error probabilistic polynomial time.

In particular, under the same assumption, this rules out the possibility of a fully polynomial time randomised approximation scheme (FPRAS).