[Math] Finding a Graph given a chromatic polynomial

coloringgraph theory

Let $f(k) = k^6 – 6k^5 + 15k^4 – 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does indeed have chromatic polynomial equal to $f(k)$.

I have no idea how to go about finding a specific graph given a chromatic polynomial. Despite extensive searching I haven't been able to find any help on this topic.

Best Answer

Let's look at the things we can figure out easily:

  1. The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(\dotsb)(k-n+1)$.)
  2. The graph is bipartite, because $f(2) = 4$ is nonzero.
  3. When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.

From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.

For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?

Related Question