Find two graphs with same order, size and chromatic number, but with different chromatic polynomial

coloringgraph theory

I'll call two graphs chromatically equivalent if they have the same chromatic polynomial. It is easy to show that two chromatically equivalent graphs must have the same order, size and chromatic number.

I want to find a counterexample of the converse, i.e., find two graphs with the same order, size and chromatic number but different chromatic polynomials. So far I've tried with every pair of graphs of order equal or less than $4$ and didn't found an example. What is the simplest example of such pair?

Best Answer

Since trees won't work, the next simplest thing to try is two unicyclic graphs.

The graphs

enter image description here and enter image description here

both have $5$ vertices, $5$ edges, and chromatic number $3$.

  • The first graph has chromatic polynomial $k(k-1)^3(k-2)$ since we can just color the vertices in order starting from the degree-$1$ vertex.

  • The second graph has chromatic polynomial $k(k-1)^3(k-2)+k(k-1)(k-2)$: if we number the vertices $1,2,3,4,5$ and color them in that order, then we usually have $k$, $k-1$, $k-1$, $k-1$, $k-2$ choices, unless we color $1$ and $4$ the same color, in which case we have $1$ extra choice for coloring $5$.

Related Question