[Math] Chromatic Polynomials for Graphs

graph theory

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

Deletion contraction step 1

and

Deletion contraction step 2.

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

Using the base cases, we know

Chromatic polynomial$=k^3-k^2$,

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

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.

Related Question