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.
Appreciate any help and answers.
Best Answer
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
which we substitute into the first equation to give the chromatic polynomial:
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.