# Chromatic Polynomials for Graphs

The chromatic polynomial of a graph $G$ is the polynomial $C_G(k)$ computed recursively using the theorem of Birkhoff and Lewis. The theorem of Birkhoff and Lewis states: $c_G(k) = c_{G-e}(k) - c_{G/e}(k)$ where $e$ is any edge from $G$, and

• $G - e$ is the graph obtained from $G$ by removing edge $e$.
• $G/e$ the graph obtained from $G$ by removing $e$, identifying the end vertices of $e$, and leaving only one copy of any resulting multiple edges.

Given the graphs $K_{1,3}$ , $K_{1,5}$, $C_4$, $C_5$ and $K_4-e$ , find the chromatic polynomials and determine how many $5$-colorings exist.

-

You also need some base cases, which can be deduced from the definition of a chromatic polynomial.

• The chromatic polynomial for $K_n$ (the complete graph on $n$ vertices) is $k(k-1)\cdots(k-n)$.

• The chromatic polynomial for $\overline{K_n}$ (the null graph on $n$ vertices; i.e. no edges) is $k^n$.

The general idea is to delete/contract edges until you are left with only these base cases (or some other case you have already computed).

Here's an example of performing the deletion-contraction method on the graph $K_{1,2}$. At each step, we perform deletion/contraction on the orange edge.

We separately compute

and

.

(I've used different notation to you since I can't draw the graph in the subscript.)

Using the base cases, we know

$=k^3-k^2$,

which we substitute into the first equation to give the chromatic polynomial:

$=(k^3-k^3)-k(k-1)=k(k-1)^2.$

If you want to know the number of ways of $5$-colouring $K_{1,2}$, we simply substitute $5$ into its chromatic polynomial. It turns out there are $80$ ways to $5$-colour $K_{1,2}$.

Note: in addition to the "deletion contraction" relation, there is also an "addition identification" relation which, in some cases, will be significantly faster.

-
But if I am to draw $K_{1,3}$ like you drew, how will that look like? Your graphs look easier to use when it comes to computing polynomials, or I might be wrong. – Dream Box Dec 18 '12 at 9:39
It's essentially the same thing. You just pick an edge e, and find the two graphs formed (a) when you delete the edge and (b) when you contract the edge. If you're not at a "base case" then repeat for the graphs obtained in (a) and/or (b). – Douglas S. Stones Dec 18 '12 at 21:37
So what you've done there is.. in the first graph, you show the graph without the edge - the edge+vertices that have been "removed". Then in the second graph you take the graph above and take that other edge left and remove it. Right? Or am I not getting something right here. Though why in the second graph there are only 2 dots and not with an edge as well? – Dream Box Dec 19 '12 at 11:25
We're not removing any vertices, but rather "contracting" a pair of vertices along an edge. In the first equation, I just picked a graph to look at ($K_{1,2}$), picked an edge e and found the two graphs: 1. formed by deleting e from $K_{1,2}$, 2. formed by contracting e in $K_{1,2}$. – Douglas S. Stones Dec 19 '12 at 20:31
@DouglasS.Stones, is the chromatic polynomial you gave for a complete graph not actually the one for $n+1$ vertices? – PrimeRibeyeDeal Apr 9 '14 at 12:43