Chromatic polynomial

All non-isomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3-set:

k^{3}

. An edge and a single vertex:

k^{2}(k-1)

. The 3-path:

k(k-1)^{2}

. The 3-clique:

k(k-1)(k-2)

The chromatic polynomial is a 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 attack the four color problem. It was generalised to the Tutte polynomial by H. 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. If $P(G,k)$ denotes the number of proper colorings of G with k colors then one could establish the four color theorem by showing $P(G,4)>0$ 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 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.^[1]

Definition

All proper vertex colorings of vertex graphs with 3 vertices using k colors for

k=0,1,2,3

. The chromatic polynomial of each graph interpolates through the number of proper colorings.

The chromatic polynomial of a graph G counts the number of its proper vertex colorings. It is commonly denoted by $P_{G}(k)$ , $\chi _{G}(k)$ , $\pi _{G}(k)$ , or by $P(G,k),$ which is what we will use from now on.

For example, the path graph $P_{3}$ on 3 vertices cannot be colored at all with 0 or 1 colors. With 2 colors, it can be colored in 2 ways. With 3 colors, it can be colored in 12 ways.

Available colors $k$	0	1	2	3
Number of colorings $P(P_{3},k)$	0	0	2	12

For a graph G with n vertices, the chromatic polynomial is defined as the unique interpolating polynomial of degree at most n through the points

\left\{(0,P(G,0)),(1,P(G,1)),\cdots ,(n,P(G,n))\right\}.

If G does not contain any vertex with a self-loop, then the chromatic polynomial is a monic polynomial of degree exactly n. In fact for the above example we have:

P(P_{3},t)=t(t-1)^{2},\qquad P(P_{3},3)=12.

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,

\chi (G)=\min\{k:P(G,k)>0\}.

Examples

Chromatic polynomials for certain graphs
Triangle $K_{3}$	$t(t-1)(t-2)$
Complete graph $K_{n}$	$t(t-1)(t-2)\cdots (t-(n-1))$
Path graph $P_{n}$	$t(t-1)^{n-1}$
Any tree on n vertices	$t(t-1)^{n-1}$
Cycle $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen graph	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$

Properties

For fixed G on n vertices, the chromatic polynomial $P(G,t)$ is in fact a polynomial of degree n. By definition, evaluating the chromatic polynomial in $P(G,k)$ yields the number of k-colorings of G for $k=0,1,\cdots ,n$ . The same hold for k > n.

The expression

(-1)^{|V(G)|}P(G,-1)

yields the number of acyclic orientations of G.^[2]

The derivative evaluated at 1, $P'(G,1)$ equals the chromatic invariant, $\theta (G)$ , up to sign.

If G has n vertices, m edges, and c components $G_{1},\cdots ,G_{c}$ , then

The coefficients of $t^{0},\cdots ,t^{c-1}$ are zeros.
The coefficients of $t^{c},\cdots ,t^{n}$ are all non-zero.
The coefficient of $t^{n}$ in $P(G,t)$ is 1.
The coefficient of $t^{{n-1}}$ in $P(G,t)$ is $-m$ .
The coefficients of every chromatic polynomial alternate in signs.
The absolute values of coefficients of every chromatic polynomial form a log-concave sequence.^[3]
$\scriptstyle P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

A graph G with n vertices is a tree if and only if

P(G,t)=t(t-1)^{n-1}.

Chromatic equivalence

The three graphs with a chromatic polynomial equal to

(x-2)(x-1)^{3}x

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:

(x-1)^{{n-1}}x,

in particular,

(x-1)^{3}x

is the chromatic polynomial of both the claw graph and the path graph on 4 vertices.

Chromatic uniqueness

A graph is chromatically unique if it is determined by its chromatic polynomial, up to isomorphism. In other words, G is chromatically unique, then $P(G,t)=P(H,t)$ would imply that G and H are isomorphic.

All cycle graphs are chromatically unique.^[4]

Chromatic roots

A root (or zero) of a chromatic polynomial, called a “chromatic root”, is a value x where $P(G,x)=0$ . 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, $P(G,x)>0$ 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.^[5] A result of Tutte connects the golden ratio $\phi$ with the study of chromatic roots, showing that chromatic roots exist very close to $\phi ^{2}$ : If $G_{n}$ is a planar triangulation of a sphere then

P(G_{n},\phi ^{2})\leq \phi ^{5-n}.

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.^[6]

Categorification

The chromatic polynomial is categorified by a homology theory closely related to Khovanov homology.^[7]

Algorithms

Chromatic polynomial
Input	Graph G with n vertices.
Output	Coefficients of $P(G,t)$
Running time	$O(2^{n}n^{r})$ for some constant $r$
Complexity	#P-hard
Reduction from	#3SAT

#k-colorings
Input	Graph G with n vertices.
Output	$P(G,k)$
Running time	In P for $k=0,1,2$ . $O(1.6262^{n})$ for $k=3$ . Otherwise $O(2^{n}n^{r})$ for some constant $r$
Complexity	#P-hard unless $k=0,1,2$
Approximability	No FPRAS for $k>2$

Computational problems associated with the chromatic polynomial include

finding the chromatic polynomial $P(G,t)$ of a given graph G;
evaluating $P(G,k)$ at a fixed point k for given G.

The first problem is more general because if we knew the coefficients of $P(G,t)$ 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 k and has been intensively studied in computational complexity. When k is a natural number, this problem is normally viewed as computing the number of k-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^[8] and graphs of bounded clique-width.^[9] The latter class includes cographs and graphs of bounded tree-width, such as outerplanar graphs.

Humans placed in a network attempting to collectively solve a graph coloring problem are assisted by noisy autonomous agents, especially when the chromatic polynomial of the graph is high.^[10]

Deletion–contraction

A recursive way of computing the chromatic polynomial is based on edge contraction: for a pair of vertices $u$ and $v$ the graph $G/uv$ is obtained by merging the two vertices and removing any edges between them. Then the chromatic polynomial satisfies the recurrence relation

P(G,k)=P(G-uv,k)-P(G/uv,k)

where $u$ and $v$ are adjacent vertices and $G-uv$ is the graph with the edge $uv$ removed. Equivalently,

P(G,k)=P(G+uv,k)+P(G/uv,k)

if $u$ and $v$ are not adjacent and $G+uv$ is the graph with the edge $uv$ added. In the first form, the recurrence terminates in a collection of empty graphs. In the second form, it terminates in a collection of complete graphs. These recurrences are also called the Fundamental Reduction Theorem.^[11] Tutte’s curiosity about which other graph properties satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial.

The expressions give rise to a recursive procedure, called the deletion–contraction algorithm, which forms the basis of many algorithms for graph coloring. The ChromaticPolynomial function in the computer algebra system Mathematica uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse.^[12] 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

\phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),

on a graph with n vertices and m edges.^[13] The analysis can be improved to within a polynomial factor of the number $t(G)$ of spanning trees of the input graph.^[14] 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

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 $i$ and $j$ being given the same color is equivalent to the $i$ ’th and $j$ ’th coordinate in the coloring vector being equal, each edge can be associated with a hyperplane of the form $\{x\in R^{d}:x_{i}=x_{j}\}$ . 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. Restricting to a set of $k$ colors, the lattice points are contained in the cube $[0,k]^{n}$ . In this context the chromatic polynomial counts the number of lattice points in the $[0,k]$ -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-complete problem, so the problem of computing the coefficients of the chromatic polynomial is #P-hard. Similarly, evaluating $P(G,3)$ for given G is #P-complete. On the other hand, for $k=0,1,2$ it is easy to compute $P(G,k)$ , so the corresponding problems are polynomial-time computable. For integers $k>3$ the problem is #P-hard, which is established similar to the case $k=3$ . In fact, it is known that $P(G,x)$ is #P-hard for all x (including negative integers and even all complex numbers) except for the three “easy points”.^[15] Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood.

In the expansion

P(G,t)=a_{1}t+a_{2}t^{2}+\dots +a_{n}t^{n},

the coefficient $a_{n}$ 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 a_r for a fixed r and a given graph G is #P-hard.^[16]

No approximation algorithms for computing $P(G,x)$ are known for any x except for the three easy points. At the integer points $k=3,4,\dots$ , 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). For other points, more complicated arguments are needed, and the question is the focus of active research. As of 2008, it is known that there is no FPRAS for computing $P(G,x)$ for any x > 2, unless NP = RP holds.^[17]

Notes

↑ Several chapters Biggs (1993)
↑ Stanley (1973)
↑ Huh (2012)
↑ Chao & Whitehead (1978)
↑ Jackson (1993)
↑ Sokal (2004)
↑ Helme-Guizon & Rong (2005)
↑ Naor, Naor & Schaffer (1987).
↑ Giménez, Hliněný & Noy (2005); Makowsky et al. (2006).
↑ Shirado, Hirokazu; Christakis, Nicholas A. "Locally noisy autonomous agents improve global human coordination in network experiments". Nature. 545 (7654): 370–374. doi:10.1038/nature22332.
↑ Dong, Koh & Teo (2005)
↑ Pemmaraju & Skiena (2003)
↑ Wilf (1986)
↑ Sekine, Imai & Tani (1995)
↑ Jaeger, Vertigan & Welsh (1990), based on a reduction in (Linial 1986).
↑ Oxley & Welsh (2002)
↑ Goldberg & Jerrum (2008)

References

Biggs, N. (1993), Algebraic Graph Theory, Cambridge University Press, ISBN 0-521-45897-8
Chao, C.-Y.; Whitehead, E. G. (1978), "On chromatic equivalence of graphs", Theory and Applications of Graphs, Lecture Notes in Mathematics, 642, Springer, pp. 121–131, ISBN 978-3-540-08666-6
Dong, F. M.; Koh, K. M.; Teo, K. L. (2005), Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Company, ISBN 981-256-317-2
Giménez, O.; Hliněný, P.; Noy, M. (2005), "Computing the Tutte polynomial on graphs of bounded clique-width", Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, 3787, Springer-Verlag, pp. 59–68, doi:10.1007/11604686_6
Goldberg, L.A.; Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation, 206 (7): 908, doi:10.1016/j.ic.2008.04.003
Helme-Guizon, Laure; Rong, Yongwu (2005), "A categorification of the chromatic polynomial", Algebraic & Geometric Topology, 5 (4): 1365–1388, doi:10.2140/agt.2005.5.1365
Huh, J. (2012), Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, arXiv:1008.4749v3
Jackson, B. (1993), "A Zero-Free Interval for Chromatic Polynomials of Graphs", Combinatorics, Probability and Computing, 2: 325–336, doi:10.1017/S0963548300000705
Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society, 108: 35–53, doi:10.1017/S0305004100068936
Linial, N. (1986), "Hard enumeration problems in geometry and combinatorics", SIAM J. Algebraic Discrete Methods, 7 (2): 331–335, doi:10.1137/0607036
Makowsky, J. A.; Rotics, U.; Averbouch, I.; Godlin, B. (2006), "Computing graph polynomials on graphs of bounded clique-width", Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, 4271, Springer-Verlag, pp. 191–204, doi:10.1007/11917496_18
Naor, J.; Naor, M.; Schaffer, A. (1987), "Fast parallel algorithms for chordal graphs", Proc. 19th ACM Symp. Theory of Computing (STOC '87), pp. 355–364, doi:10.1145/28395.28433 .
Oxley, J. G.; Welsh, D. J. A. (2002), "Chromatic, flow and reliability polynomials: The complexity of their coefficients.", Combinatorics, Probability and Computing, 11 (4): 403–426
Pemmaraju, S.; Skiena, S. (2003), Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, section 7.4.2, ISBN 0-521-80686-0
Sekine, K.; Imai, H.; Tani, S. (1995), "Computing the Tutte polynomial of a graph of moderate size", Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004, Cairns, Australia, December 4–6, 1995: Springer, pp. 224–233
Sokal, A. D. (2004), "Chromatic Roots are Dense in the Whole Complex Plane", Combinatorics, Probability and Computing, 13 (2): 221–261, doi:10.1017/S0963548303006023
Stanley, R. P. (1973), "Acyclic orientations of graphs", Disc. Math., 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8
Voloshin, Vitaly I. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications., American Mathematical Society, ISBN 0-8218-2812-6
Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall, ISBN 0-13-021973-8

External links

Weisstein, Eric Wolfgang. "Chromatic polynomial". MathWorld.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.