Editing Chromatic polynomial (section)

==Algorithms==
{{infobox
| above = Chromatic polynomial
| abovestyle = background: #DD9; font-size: 125%;
| labelstyle = font-weight:normal
| label1 = Input
| data1 = Graph ''G'' with ''n'' vertices.
| label2 = Output
| data2 = Coefficients of <math>P(G, x)</math>
| label3 = Running time
| data3 = <math>O(2^nn^r)</math> for some constant <math>r</math>
| label4 = Complexity
| data4 = [[Sharp-P|#P]]-hard
| label5 = Reduction from
| data5 =<nowiki>#</nowiki>3SAT
}}
{{infobox
| above =<nowiki>#</nowiki>k-colorings
| abovestyle = background: #DD9; font-size: 125%;
| labelstyle = font-weight:normal
| label1 = Input
| data1 = Graph ''G'' with ''n'' vertices.
| label2 = Output
| data2 = <math>P(G, k)</math>
| label3 =Running time
| data3 = In [[P (complexity class)|P]] for <math>k=0,1,2</math>. <math>O(1.6262^n)</math> for  <math>k=3</math>. Otherwise
<math>O(2^nn^r)</math> for some constant <math>r</math>
| label4 =Complexity
| data4 = [[Sharp-P|#P]]-hard unless <math>k=0,1,2</math>
| label5 = Approximability
| data5 =  No FPRAS for <math>k>2</math>
}}

Computational problems associated with the chromatic polynomial include

* finding the chromatic polynomial <math>P(G, x)</math> of a given graph ''G'';
* evaluating <math>P(G, x)</math> at a fixed ''x'' for given ''G''.

The first problem is more general because if we knew the coefficients of <math>P(G, x)</math> 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 theory|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  [[Sharp-P|#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 graph]]s<ref>{{harvtxt|Naor|Naor|Schaffer|1987}}.</ref> and graphs of bounded [[clique-width]].<ref>{{harvtxt|Giménez|Hliněný|Noy|2005}}; {{harvtxt|Makowsky|Rotics|Averbouch|Godlin|2006}}.</ref> The latter class includes [[cograph]]s and graphs of bounded [[tree-width]], such as [[outerplanar graph]]s.

===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.<ref>{{harvtxt|Pemmaraju|Skiena|2003}}</ref> 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

:<math>\varphi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1.62^{n+m}\right),</math>

on a graph with ''n'' vertices and ''m'' edges.<ref>{{harvtxt|Wilf|1986}}</ref> The analysis can be improved to within a polynomial factor of the number <math>t(G)</math> of [[spanning tree (mathematics)|spanning trees]] of the input graph.<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref> In practice, [[branch and bound]] strategies and [[isomorphism|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 <math>i</math> and <math>j</math> being given the same color is equivalent to the <math>i</math>’th and <math>j</math>’th coordinate in the coloring vector being equal, each edge can be associated with a hyperplane of the form <math>\{x\in\mathbb R^d:x_i=x_j\}</math>. The collection of such hyperplanes for a given graph is called its '''graphic [[arrangement of hyperplanes|arrangement]]'''. The proper colorings of a graph are those lattice points which avoid forbidden hyperplanes.
Restricting to a set of <math>k</math> colors, the lattice points are contained in the cube <math>[0,k]^n</math>. In this context the chromatic polynomial counts the number of lattice points in the <math>[0,k]</math>-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 [[Sharp-P|#P]]-complete problem, so the problem of computing the coefficients of the chromatic polynomial is #P-hard. Similarly, evaluating <math>P(G, 3)</math> for given ''G'' is #P-complete. On the other hand, for <math>k=0,1,2</math> it is easy to compute <math>P(G, k)</math>, so the corresponding problems are polynomial-time computable. For integers <math>k>3</math> the problem is #P-hard, which is established similar to the case <math>k=3</math>. In fact, it is known that <math>P(G, x)</math> is #P-hard for all ''x'' (including negative integers and even all [[complex number]]s) except for the three “easy points”.<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}, based on a reduction in {{harv|Linial|1986}}.</ref> Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood.

In the expansion

:<math>P(G, x)= a_1 x + a_2x^2+\cdots +a_nx^n,</math>

the coefficient <math>a_n</math> 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<sub>r</sub>'' for a fixed ''r ≥ 1'' and a given graph ''G'' is #P-hard, even for bipartite planar graphs.<ref>{{harvtxt|Oxley|Welsh|2002}}</ref>

No [[approximation algorithms]] for computing <math>P(G, x)</math> are known for any ''x'' except for the three easy points. At the integer points <math>k=3,4,\ldots</math>, 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&nbsp;=&nbsp;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 [[FPRAS|fully polynomial time randomised approximation scheme (FPRAS)]]. There is no [[FPRAS]] for computing <math>P(G, x)</math> for any ''x'' > 2, unless [[NP (complexity class)|NP]]&nbsp;=&nbsp;[[RP (complexity class)|RP]] holds.<ref>{{harvtxt|Goldberg|Jerrum|2008}}</ref>