= Chromatic polynomial
{title2=$P_G(t)$}
{wiki}
The chromatic polynomial turns a <graph coloring> problem into a counting problem: \b[how many choices remain when adjacent <vertices> must have different colours?] For a finite <simple graph> $G$ and a positive <integer> $t$, $P_G(t)$ is the number of <proper vertex colorings> using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a <polynomial>, its values at arbitrary noninteger arguments are not counts of colourings.
Consider the three-vertex <path graph> $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The <multiplication principle> gives
$$
P_{P_3}(t)=t(t-1)^2=t^3-2t^2+t.
$$
Adding the <edge> $AC$ makes the three-vertex <complete graph> $K_3$. Now $C$ must avoid both preceding colours, so
$$
P_{K_3}(t)=t(t-1)(t-2)=t^3-3t^2+2t.
$$
With three available colours, the <path graph> has \b[12 colourings], whereas the triangle has \b[6]. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.
\Image[/chromatic-polynomial-path-colorings.png]
{title=All twelve proper colourings of a three-vertex path using a three-colour palette}
For a nonempty <graph>, the <chromatic number> records only the first positive <integer> $t$ for which $P_G(t)>0$. The <chromatic polynomial> also counts the choices for every larger palette. For the path the <chromatic number> is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent <vertices> represent tasks that must use different slots, the <chromatic polynomial> counts the valid assignments to $t$ named slots. Adding a conflict <edge> can only remove assignments.
The <chromatic polynomial> also remembers some of the graph's structure. For a <simple graph> with $n\geq 1$ <vertices> and $m$ <edges>, its leading terms are $t^n-mt^{n-1}$; its <degree of a polynomial> gives the number of <vertices>, and its next coefficient gives the number of <edges>. It does not determine the graph completely. A four-vertex <path graph> and a four-vertex <star graph> are not related by a <graph isomorphism>, but both are <trees> and have <chromatic polynomial> $t(t-1)^3$.
The early connection to map colouring appears in George D. Birkhoff's article https://www.jstor.org/stable/1967597[A Determinant Formula for the Number of Ways of Coloring a Map, Annals of Mathematics 14 (1912–1913), pp. 42–46]{ref}. For a derivation of the counting recurrence and its leading coefficients, see https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecturex9.html[Paul Johnson's MAS 341 lecture on chromatic polynomials].
Back to article page