View source for Chromatic polynomial

{{Short description|Function in algebraic graph theory}}
[[File:Chromatic polynomial of all 3-vertex graphs BW.png|thumb|250px|right|All non-isomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3-set: {{math|''k''{{sup|3}}}}. An edge and a single vertex: {{math|''k''{{sup|2}}(''k'' – 1)}}. The 3-path: {{math|''k''(''k'' – 1){{sup|2}}}}. The 3-clique: {{math|''k''(''k'' – 1)(''k'' – 2)}}.]]

The '''chromatic polynomial''' is a [[graph polynomial]] studied in [[algebraic graph theory]], a branch of [[mathematics]]. It counts the number of [[graph coloring]]s 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 graph]]s, in an attempt to prove the [[four color theorem]]. If <math>P(G, k)</math> denotes the number of proper colorings of ''G'' with ''k'' colors then one could establish the four color theorem by showing <math>P(G, 4)>0</math> for all planar graphs ''G''. In this way he hoped to apply the powerful tools of [[mathematical analysis|analysis]] and [[abstract algebra|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.<ref>{{harvtxt|Read|1968}}</ref> Today, chromatic polynomials are one of the central objects of [[algebraic graph theory]].<ref>Several chapters {{harvtxt|Biggs|1993}}</ref>

==Definition==
[[File:Chromatic polynomial of all 3-vertex graphs BW with colorings.png|thumb|300px|right|All proper vertex colorings of vertex graphs with 3 vertices using ''k'' colors for <math>k=0,1,2,3</math>. The chromatic polynomial of each graph interpolates through the number of proper colorings.]]

For a graph ''G'', <math>P(G,k)</math> counts the number of its (proper) [[vertex coloring|vertex ''k''-colorings]]. 
Other commonly used notations include <math>P_G(k)</math>, <math>\chi_G(k)</math>, or <math>\pi_G(k)</math>.
There is a unique [[polynomial]] <math>P(G,x)</math> which evaluated at any integer ''k'' ≥ 0 coincides with <math>P(G,k)</math>; it is called the '''chromatic polynomial''' of ''G''.

For example, to color the [[path graph]] <math>P_3</math> on 3 vertices with ''k'' colors, one may choose any of the ''k'' colors for the first vertex, any of the <math>k - 1</math> remaining colors for the second vertex, and lastly for the third vertex, any of the <math>k - 1</math> colors that are different from the second vertex's choice.
Therefore, <math>P(P_3,k) = k \cdot (k-1) \cdot (k-1)</math> is the number of ''k''-colorings of <math>P_3</math>.
For a variable ''x'' (not necessarily integer), we thus have <math>P(P_3,x)=x(x-1)^2=x^3-2x^2+x</math>.
(Colorings which differ only by permuting colors or by [[graph automorphism|automorphisms]] of ''G'' are still counted as different.)

===Deletion–contraction===
{{Main|Deletion–contraction formula}}
The fact that the number of ''k''-colorings is a polynomial in ''k'' follows from a recurrence relation called the '''[[Deletion–contraction formula|deletion–contraction recurrence]]''' or '''Fundamental Reduction Theorem'''.<ref>{{harvtxt|Dong|Koh|Teo|2005}}</ref> It is based on [[edge contraction]]: for a  pair of vertices <math>u</math> and <math>v</math> the graph <math>G/uv</math> is obtained by merging the two vertices and removing any edges between them. 
If <math>u</math> and <math>v</math> are adjacent in ''G'', let <math>G-uv</math> denote the graph obtained by removing the edge <math>uv</math>.
Then the numbers of ''k''-colorings of these graphs satisfy:
:<math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>
Equivalently, if <math>u</math> and <math>v</math> are not adjacent in ''G'' and <math>G+uv</math> is the graph with the edge <math>uv</math> added, then
:<math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>
This follows from the observation that every ''k''-coloring of ''G'' either gives different colors to <math>u</math> and <math>v</math>, or the same colors. In the first case this gives a (proper) ''k''-coloring of <math>G+uv</math>, while in the second case it gives a coloring of <math>G/uv</math>.
Conversely, every ''k''-coloring of ''G'' can be uniquely obtained from a ''k''-coloring of <math>G+uv</math> or <math>G/uv</math> (if <math>u</math> and <math>v</math> are not adjacent in ''G'').

The chromatic polynomial can hence be recursively defined as 
:<math>P(G,x)=x^n</math> for the edgeless graph on ''n'' vertices, and 
:<math>P(G,x)=P(G-uv, x)- P(G/uv,x)</math> for a graph ''G'' with an edge <math>uv</math> (arbitrarily chosen).
Since the number of ''k''-colorings of the edgeless graph is indeed <math>k^n</math>, it follows by induction on the number of edges that for all ''G'', the polynomial <math>P(G,x)</math> coincides with the number of ''k''-colorings at every integer point ''x''&nbsp;=&nbsp;''k''. In particular, the chromatic polynomial is the unique [[interpolating polynomial]] of degree at most ''n'' through the points
:<math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \ldots, (n, P(G, n)) \right \}.</math>

[[Tutte]]’s curiosity about which other [[graph invariant]]s satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the [[Tutte polynomial]] <math>T_G(x,y)</math>.

==Examples==
{| class="wikitable" 
|+Chromatic polynomials for certain graphs
|-
| Triangle <math>K_3</math> || <math>x(x-1)(x-2)</math>
|-
| [[Complete graph]] <math>K_n</math> || <math>x(x-1)(x-2)\cdots(x-(n-1))</math>
|-
| [[Edgeless graph]] <math>\overline K_n</math> || <math>x^n</math>
|-
| [[Path graph]] <math>P_n</math> || <math>x(x-1)^{n-1}</math>
|-
| Any [[Tree graph|tree]] on ''n'' vertices || <math>x(x-1)^{n-1}</math>   
|-
| [[Cycle graph|Cycle]] <math>C_n</math>|| <math>(x-1)^n+(-1)^n(x-1)</math>
|-
| [[Petersen graph]] || <math>x(x-1)(x-2) \left (x^7-12x^6+67x^5-230x^4+529x^3-814x^2+775x-352 \right)</math>
|}

==Properties==
For fixed ''G'' on ''n'' vertices, the chromatic polynomial <math>P(G, x)</math> is a [[monic polynomial|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,
: <math>\chi (G)=\min\{ k\in\mathbb{N} : P(G, k) > 0 \}.</math>

The polynomial evaluated at <math>-1</math>, that is <math>P(G,-1)</math>, yields <math>(-1)^{|V(G)|}</math> times the number of [[acyclic orientation]]s of ''G''.<ref>{{harvtxt|Stanley|1973}}</ref>

The derivative evaluated at 1, <math>P'(G, 1)</math> equals the [[chromatic invariant]] <math>\theta(G)</math> up to sign.
 
If ''G'' has ''n'' vertices and ''c'' [[connected component (graph theory)|components]] <math>G_1, \ldots, G_c</math>, then
* The coefficients of <math> x^0, \ldots, x^{c-1}</math> are zeros.
* The coefficients of <math> x^c, \ldots, x^n</math> are all non-zero and alternate in signs.
* The coefficient of <math>x^n</math> is 1 (the polynomial is [[monic polynomial|monic]]).
* The coefficient of <math>x^{n-1}</math> is <math>-|E(G)|. </math>

We prove this via induction on the number of edges on a simple graph ''G'' with <math>n</math> vertices and <math>k</math> edges. When <math>k = 0</math>, ''G'' is an empty graph. Hence per definition <math>P(G, x)= x^n</math>. So the coefficient of <math>x^{n-1}</math> is <math>0</math>, which implies the statement is true for an empty graph. When <math>k = 1</math>, as in ''G'' has just a single edge, <math>P(G, x) = x^n - x^{n-1}</math>. Thus coefficient of <math>x^{n-1}</math> is <math>-1 = -|E(G)|</math>. So the statement holds for k = 1. Using [[strong induction]]  assume the statement is true for <math>k = 0,1,2,\ldots,(k-1)</math>. Let ''G'' have <math>k</math> edges. By the [[Deletion-contraction formula|contraction-deletion principle]], <blockquote><math> P(G, x) = P(G-e, x) - P(G/e, x),</math> </blockquote>Let <math>P(G-e, x) = x^n - a_{n-1}x^{n-1} + a_{n-2}x^{n-2}-\cdots,</math> and <math>P(G/e, x) = x^{n-1} - b_{n-2} x^{n-2} + b_{n-3}x^{n-3}-\cdots.</math> <br>Hence <math>P(G, x) = x^n - (a_{n-1} +1)x^{n-1} +\cdots</math>.<br>Since <math>G-e</math> is obtained from ''G'' by removal of just one edge ''e'', <math>a_{n-1} = k - 1</math>, so <math>a_{n-1} + 1 = k</math> and thus the statement is true for ''k''.

* The coefficient of <math>x^1</math> is <math>(-1)^{n-1}</math> times the number of acyclic orientations that have a unique sink, at a specified, arbitrarily chosen vertex.<ref>{{harvtxt|Ellis-Monaghan|Merino|2011}}</ref>
* The absolute values of coefficients of every chromatic polynomial form a [[Logarithmically concave sequence|log-concave sequence]].<ref>{{harvtxt|Huh|2012}}</ref>
* <math>\scriptstyle P(G, x) = P(G_1, x)P(G_2,x) \cdots P(G_c,x)</math>

The last property is generalized by the fact that if ''G'' is a [[Clique-sum|''k''-clique-sum]] of <math>G_1</math> and <math>G_2</math> (i.e., a graph obtained by gluing the two at a clique on ''k'' vertices), then
:<math>P(G, x) = \frac{P(G_1,x)P(G_2,x)}{x(x-1)\cdots(x-k+1)}.</math>

A graph ''G'' with ''n'' vertices is a tree if and only if 
:<math>P(G, x) = x(x-1)^{n-1}.</math>

===Chromatic equivalence===
[[File:Chromatically equivalent graphs.svg|thumb|right|250px|{{center|The three graphs with a chromatic polynomial equal to <math>(x-2)(x-1)^3x</math>.}}]]

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, <math>(x-1)^3x</math> is the chromatic polynomial of both the [[claw (graph theory)|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'' is chromatically unique, then <math>P(G, x) = P(H, x)</math> would imply that ''G'' and ''H'' are isomorphic.
All [[cycle graph]]s are chromatically unique.<ref>{{harvtxt|Chao|Whitehead|1978}}</ref>

===Chromatic roots===
A [[root of a function|root]] (or ''zero'') of a chromatic polynomial, called a “chromatic root”, is a value ''x'' where <math>P(G, x)=0</math>. 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, <math>P(G, x)>0</math> 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.<ref>{{harvtxt|Jackson|1993}}</ref> A result of Tutte connects the [[golden ratio]] <math>\varphi</math> with the study of chromatic roots, showing that chromatic roots exist very close to <math>\varphi^2</math>:
If <math>G_n</math> is a planar triangulation of a sphere then

:<math>P(G_n,\varphi^2) \leq \varphi^{5-n}.</math>

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.<ref>{{harvtxt|Sokal|2004}}</ref>

===Colorings using all colors===
For a graph ''G'' on ''n'' vertices, let <math>e_k</math> 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 [[Graph automorphism|automorphisms]] of ''G'' are still counted separately).
In other words, <math>e_k</math> counts the number of [[Partition of a set|partitions]] of the vertex set into ''k'' (non-empty) [[Independent set (graph theory)|independent sets]].
Then <math>k! \cdot e_k</math> 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:
: <math>P(G,x) = \sum_{k=0}^x \binom{x}{k} k! \cdot e_k = \sum_{k=0}^x (x)_k \cdot e_k,</math>
where <math>(x)_k = x(x-1)(x-2)\cdots(x-k+1)</math> denotes the [[falling factorial]].
Thus the numbers <math>e_k</math> are the coefficients of the polynomial <math>P(G,x)</math> in the basis <math>1,(x)_1,(x)_2,(x)_3,\ldots</math> of falling factorials.

Let <math>a_k</math> be the ''k''-th coefficient of <math>P(G,x)</math> in the standard basis <math>1,x,x^2,x^3,\ldots</math>, that is:
: <math>P(G,x) = \sum_{k=0}^n a_k x^k</math>
[[Stirling number]]s give a [[Stirling number#As change of basis coefficients|change of basis]] between the standard basis and the basis of falling factorials.
This implies:
:<math>a_k = \sum_{j=0}^n (-1)^{j-k} \begin{bmatrix}j\\k\end{bmatrix} e_j</math> &nbsp; and &nbsp; <math>e_k = \sum_{j=0}^n \begin{Bmatrix}j\\k\end{Bmatrix} a_j. </math>

===Categorification===
The chromatic polynomial is [[categorification|categorified]] by a homology theory closely related to [[Khovanov homology]].<ref>{{harvtxt|Helme-Guizon|Rong|2005}}</ref>

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

==See also==
* [[Chromatic symmetric function]]

==Notes==
{{reflist|2}}

== References ==
{{refbegin|2}}
*{{Citation
|last=Biggs | first=N.
|title=Algebraic Graph Theory
|publisher=Cambridge University Press
|year=1993
|isbn=978-0-521-45897-9
}}
*{{Citation
|last1=Chao | first1=C.-Y.
|last2=Whitehead | first2=E. G.
|contribution=On chromatic equivalence of graphs
|title=Theory and Applications of Graphs
|year=1978
|volume=642
|pages=121–131
|publisher=Springer
|series=Lecture Notes in Mathematics
|isbn=978-3-540-08666-6
}}
*{{Citation
|last1= Dong | first1= F. M.
|last2= Koh | first2= K. M.
|last3=  Teo| first3= K. L.
|title=Chromatic polynomials and chromaticity of graphs
|publisher=World Scientific Publishing Company
|year=2005
|isbn= 978-981-256-317-0
}}
* {{citation|title=Structural Analysis of Complex Networks 
|chapter=Graph polynomials and their applications I: The Tutte polynomial 
|first1=Joanna A. |last1=Ellis-Monaghan | author1-link = Jo Ellis-Monaghan
|first2=Criel |last2=Merino 
|arxiv=0803.3079
|date=2011
|isbn=978-0-8176-4789-6
|editor-last=Dehmer |editor-first=Matthias
|language=en-gb 
|doi=10.1007/978-0-8176-4789-6_9
|s2cid=585250 
}}
*{{citation
 | last1 = Giménez | first1 = O.
 | last2 = Hliněný | first2 = P.
 | last3 = Noy | first3 = M.
 | contribution = Computing the Tutte polynomial on graphs of bounded clique-width
 | doi = 10.1007/11604686_6
 | pages = 59–68
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005)
 | volume = 3787
 | year = 2005| isbn = 978-3-540-31000-6
 | citeseerx = 10.1.1.353.6385
 }}
*{{Citation
|last1=Goldberg | first1= L.A. | author1-link = Leslie Ann Goldberg
|last2=Jerrum | first2=  M.
|author2-link=Mark Jerrum
|title= Inapproximability of the Tutte polynomial
|journal=Information and Computation
| doi= 10.1016/j.ic.2008.04.003    
|year=2008
|volume=206
|pages=908
|issue=7
|arxiv=cs/0605140
| s2cid= 53304001 }}
*{{Citation
|last1=Helme-Guizon | first1=Laure
|last2=Rong | first2=Yongwu
|title=A categorification of the chromatic polynomial
|journal=Algebraic & Geometric Topology
| doi= 10.2140/agt.2005.5.1365   
|year=2005
|volume=5
|pages=1365–1388
|issue=4
|arxiv=math/0412264| s2cid=1339633
}}
*{{citation
 | last = Huh | first = June
 | arxiv = 1008.4749
 | doi = 10.1090/S0894-0347-2012-00731-0
 | issue = 3
 | journal = Journal of the American Mathematical Society
 | mr = 2904577
 | pages = 907–927
 | title = Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
 | volume = 25
 | year = 2012| s2cid = 13523955
 }}
*{{Citation
| doi= 10.1017/S0963548300000705
| last1= Jackson |first1= B.
| title= A Zero-Free Interval for Chromatic Polynomials of Graphs
|journal=Combinatorics, Probability and Computing
| volume= 2| issue= 3 |pages = 325–336
| year= 1993
| s2cid= 39978844 }}
*{{Citation
| doi= 10.1017/S0305004100068936
| last1= Jaeger |first1= F.
| last2= Vertigan | first2=  D. L.
| last3= Welsh | first3  =D. J. A. | authorlink3=Dominic Welsh
| title= On the computational complexity of the Jones and Tutte polynomials
| journal=[[Mathematical Proceedings of the Cambridge Philosophical Society]]
| volume= 108| issue= 1 |pages = 35–53
| year= 1990
|bibcode= 1990MPCPS.108...35J| s2cid= 121454726 }}
*{{Citation
|doi=10.1137/0607036
|last=Linial | first=N. | authorlink = Nati Linial
|title=Hard enumeration problems in geometry and combinatorics
|journal= SIAM J. Algebr. Discrete Methods
|volume= 7|issue=2|pages=331–335|year= 1986
}} 
*{{citation
 | last1 = Makowsky | first1 = J. A.
 | last2 = Rotics | first2 = U.
 | last3 = Averbouch | first3 = I.
 | last4 = Godlin | first4 = B.
 | contribution = Computing graph polynomials on graphs of bounded clique-width
 | doi = 10.1007/11917496_18
 | pages = 191–204
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)
 | volume = 4271
 | year = 2006| isbn = 978-3-540-48381-6
 | citeseerx = 10.1.1.76.2320
 }}
*{{citation
 | last1 = Naor | first1 = J.
 | last2 = Naor | first2 = M.
 | last3 = Schaffer | first3 = A.
 | contribution = Fast parallel algorithms for chordal graphs
 | doi = 10.1145/28395.28433
 | pages = 355–364
 | title = Proc. 19th ACM Symp. Theory of Computing (STOC '87)
 | year = 1987| isbn = 978-0897912211
 | s2cid = 12132229
 | doi-access = free
 }}.
*{{Citation
|last1=Oxley | first1=J. G.
|last2=Welsh | first2=D. J. A.
|title=Chromatic, flow and reliability polynomials: The complexity of their coefficients.
|journal=[[Combinatorics, Probability and Computing]]
|volume=11
|year=2002
|issue=4
|pages=403–426
| doi=10.1017/S0963548302005175
| s2cid=14918970
}}
*{{Citation
|last1=Pemmaraju | first1=S.
|last2= Skiena | first2= S.
|title= Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica
|publisher=Cambridge University Press
|year=2003
|at=section 7.4.2
|isbn=978-0-521-80686-2
}}
*{{Citation
|last=Read | first=R. C. | author-link=Ronald C. Read
|title=An introduction to chromatic polynomials
|journal=[[Journal of Combinatorial Theory]]
|year=1968
|pages=52–71
|volume=4
|doi=10.1016/S0021-9800(68)80087-0
|url=http://dml.cz/bitstream/handle/10338.dmlcz/128421/CzechMathJ_43-1993-3_10.pdf
|doi-access=free
}}
*{{citation
 | last1 = Sekine | first1 = Kyoko
 | last2 = Imai | first2 = Hiroshi
 | last3 = Tani | first3 = Seiichiro
 | editor1-last = Staples | editor1-first = John
 | editor2-last = Eades | editor2-first = Peter
 | editor3-last = Katoh | editor3-first = Naoki
 | editor4-last = Moffat | editor4-first = Alistair
 | contribution = Computing the Tutte polynomial of a graph of moderate size
 | doi = 10.1007/BFb0015427
 | pages = 224–233
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4–6, 1995, Proceedings
 | volume = 1004
 | year = 1995| isbn = 978-3-540-60573-7
 }}
*{{Citation
|doi=10.1017/S0963548303006023
|last=Sokal | first=A. D. |author-link=Alan Sokal
|title=Chromatic Roots are Dense in the Whole Complex Plane
|journal=[[Combinatorics, Probability and Computing]] |year=2004 |pages= 221–261|volume= 13
|issue=2 
|arxiv=cond-mat/0012369|s2cid=5549332 }}
*{{Citation
| doi=10.1016/0012-365X(73)90108-8
| last=Stanley |first= R. P.
|title= Acyclic orientations of graphs
|journal= [[Discrete Mathematics (journal)|Discrete Math.]] 
|volume=5 |pages=171–178|year= 1973
| issue=2
|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf
}}
*{{Citation
| last= Voloshin | first= Vitaly I.
| title= Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. 
| publisher=  American Mathematical Society 
| year  =2002
| isbn= 978-0-8218-2812-0
}}
*{{Citation
| last= Wilf | first= H. S. | author-link=Herbert Wilf
| title= Algorithms and Complexity
| publisher=  Prentice–Hall
| year  =1986
| isbn= 978-0-13-021973-2
}}
{{refend}}

== External links ==
* {{MathWorld | urlname=ChromaticPolynomial| title=Chromatic polynomial|mode=cs2}}
* [[PlanetMath]] [http://planetmath.org/encyclopedia/ChromaticPolynomial.html Chromatic polynomial] {{Webarchive|url=https://web.archive.org/web/20080820122306/http://planetmath.org/encyclopedia/ChromaticPolynomial.html |date=2008-08-20 }}
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [https://archive.today/20121220104146/http://www.ecs.vuw.ac.nz/~djp/tutte/]

{{DEFAULTSORT:Chromatic Polynomial}}
[[Category:Graph invariants]]
[[Category:Graph coloring]]