Editing Chromatic polynomial (section)

==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^{n-2}</math> is <math>\tbinom{|E|}{2} - t(G)</math>, where <math>t(G)</math> is the number of triangles (3-cycle subgraphs) in <math>G</math>.

* 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>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, isomorphic to the complete graph <math>K_k</math>), then
:<math>P(G, x) = \frac{P(G_1,x)P(G_2,x)}{P(K_k,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>