Bounds on the number of proper 3-colorings of cubic graphs

Question

Are there known bounds on the number of proper 3-colorings of a 3-regular in terms of vertex count?

Answer 1

I don't have a complete answer here, but some things that might help.

First I am just going to assume that we want to maximise the value $P_G(3)$ where $P_G$ is the chromatic polynomial of $G$.

There are some very general upper bounds on the value of $P_G(x)$ in terms of number of vertices and edges, but most are hopeless for regular graphs. The bound in New Bounds for Chromatic Polynomials and Chromatic Roots at least involves maximum degree and may help.

For lower bounds you need to find a family with many $3$-colourings. The best that I know is the family of cubic graphs on $6n$ vertices obtained by taking $n$ copies of the bipartite graph $K_{3,3}$, deleting an edge from each of them (creating two vertices of degree two) and then connecting each copy of $K_{3,3}$ to the next in a cyclic fashion using the vertices of degree two.

As a picture is worth 1000 words, here is a picture of this graph with $n = 4$ copies of $K_{3,3}$.

By some standard messing around with recurrence relations we can deduce that the chromatic polynomial of the member of this family with $n$ four-cycles (and hence $6n$ vertices) is

$$(x-1) \left(4 x^2-16 x+17\right)^n+\left((x-1)^2 \left(x^4-7 x^3+21 x^2-30 x+17\right)\right)^n$$

If we put $x=3$ into this we discover that the number of $3$-colourings of this graph is $$ 2\cdot 5^n + 32^n. $$

Replace $n$ by $n/6$ if you prefer the graph to have $n$ rather than $6n$ vertices.

By coincidence (or perhaps not?) this family of graphs is also conjectured to be the cubic graph with the maximum number of Hamilton cycles.