= Deletion-contraction recurrence for the chromatic polynomial
{title2=$P_G(t)=P_{G-e}(t)-P_{G/e}(t)$}
Deleting an edge removes one colour constraint. <Edge contraction> describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct <vertices> $u,v$ of a <simple graph> $G$, write $G-e$ for the <graph> with that <edge> deleted and $G/e$ for the <graph> with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a <proper vertex coloring>. Then
$$
P_G(t)=P_{G-e}(t)-P_{G/e}(t).
$$
To see why, divide the <proper vertex colorings> of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged <vertex> receives their common colour. Subtracting the second class leaves the first.
For the triangle, delete $AC$ to get a three-vertex <path graph>, or contract $AC$ to get two <vertices> joined by an <edge> after removing the redundant parallel edge. Consequently,
$$
P_{K_3}(t)=t(t-1)^2-t(t-1)=t(t-1)(t-2).
$$
At $t=3$, this says \b[$6=12-6$]. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.
\Image[/chromatic-polynomial-deletion-contraction.png]
{title=Deleting and contracting a triangle edge separates the allowed and newly forbidden colourings}
This recurrence is useful because it reduces a constrained counting problem to smaller <graphs>. A <graph> on $n$ <vertices> with no <edges> has $P_G(t)=t^n$, since every <vertex> chooses its colour independently. Repeated <edge> deletion and <edge contraction> reduce to this case and show that the counting function is a <polynomial>. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.
Back to article page
