Chromatic polynomial

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

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

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 ${\displaystyle P(G,k)}$ denotes the number of proper colorings of G with k colors then one could establish the four color theorem by showing ${\displaystyle 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.

...
Wikipedia