The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.

History

George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem denotes the number of proper colorings of G with k 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. 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. There is a unique polynomial which evaluated at any integer k; it is called the chromatic polynomial of G.

For example, to color the path graph on 3 vertices with k colors, one may choose any of the k is the number of k. For a variable x. (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 are adjacent in G. Then the numbers of k-colorings of these graphs satisfy:

are not adjacent in G added, then

This follows from the observation that every k-coloring of G, or the same colors. In the first case this gives a (proper) k. Conversely, every k-coloring of G can be uniquely obtained from a k are not adjacent in G).

The chromatic polynomial can hence be recursively defined as

1. for the edgeless graph on n vertices, and

2. for a graph G (arbitrarily chosen).

Since the number of k, it follows by induction on the number of edges that for all G 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 invariants satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial.

Examples

Properties

For fixed G on n 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,

times the number of acyclic orientations of G.

equals the chromatic invariant up to sign.

If G has n vertices and c components, then

• are zeros.

• are all non-zero and alternate in signs.

• is 1 (the polynomial is monic).

We prove this via induction on the number of edges on a simple graph G, G, as in G. So the statement holds for k = 1. Using strong induction. Let G edges. By the contraction-deletion principle, . is obtained from G by removal of just one edge e and thus the statement is true for k.

• .

  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 (i.e., a graph obtained by gluing the two at a clique on k), 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 is the chromatic polynomial of both the claw graph and the path graph on 4 vertices.

A graph is chromatically unique if it is determined by its chromatic polynomial, up to isomorphism. In other words, G would imply that G and H are isomorphic. All cycle graphs are chromatically unique.

Chromatic roots

A root (or zero) of a chromatic polynomial, called a "chromatic root", is a value x for x ≥ 4. This would have established the four color theorem.

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

Colorings using all colors

For a graph G on n 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 counts the number of partitions of the vertex set into k (non-empty) independent sets 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:

denotes the falling factorial of falling factorials.

be the k, that is:

Stirling numbers give a change of basis between the standard basis and the basis of falling factorials. This implies:

1. and

Categorification

The chromatic polynomial is categorified by a homology theory closely related to Khovanov homology.

Algorithms

Computational problems associated with the chromatic polynomial include

• of a given graph G;

• at a fixed x for given G.

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. 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. The latter class includes cographs 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 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, so in the worst case, the algorithm runs in time within a polynomial factor of

on a graph with n vertices and m edges. of spanning trees of the input graph. 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.

Cube method

. The collection of such hyperplanes for a given graph is called its graphic arrangement-cube that avoid the graphic arrangement.

Computational complexity

The problem of computing the number of 3-colorings of a given graph is a canonical example of a #P for given G is #P-hard for all x (including negative integers and even all complex numbers) except for the three "easy points". Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood.

In the expansion

is always equal to 1, and several other properties of the coefficients are known. This raises the question if some of the coefficients are easy to compute. However the computational problem of computing ar for a fixed r ≥ 1 and a given graph G is #P-hard, even for bipartite planar graphs.

No approximation algorithms are known for any x, 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). There is no FPRAS for any x > 2, unless NP=RP holds.

See also

• Chromatic symmetric function

Notes

References

• .

External links

• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: