*The following post has now been written up as Section 6 of this paper. In fact, one may show that the number of values of the chromatic polynomials at 4 grows exponentially.*

The number of chromatic polynomials grows exponentially. This answer is joint with Slava Krushkal.

The *Chromatic algebra* $\mathcal{C}_n$ is an algebra over $\mathbb{C}[Q]$ (for a parameter $Q$) formed from linear combinations of (isotopy classes of) planar graphs in a rectangle $R$ with $n$ univalent points on top and bottom:

Such diagrams may be composed by placing one on top of the other, fusing the $n$ univalent vertices together to get edges. Then quotient this algebra by some relations: the deletion-contraction relation

and a relation to eliminate loops and kill diagrams with bridges

Such diagrams represent planar graphs which agree outside of the shown pictures. These relations are satisfied by the polynomial in $Q$ which counts the number of nowhere zero flows (over an abelian group with $Q$ elemnts) in a graph. There is also a trace, where one closes up the graph top to bottom and evaluates the flow polynomial:

For generic $Q\in \mathbb{C}$, this is a semisimple algebra. More generally, one can describe a planar algebra containing all of the $\mathcal{C}_n$s.

To understand why the number of chromatic polynomials grows exponentially, the idea is to take some graphs in $\mathcal{C}_n$ which generate a semigroup in the algebra. Since the algebra is linear, the Tits alternative for semigroups implies that either this semigroup should contain a free subsemigroup or is virtually nilpotent. The latter is unlikely, if one takes generators of $\mathcal{C}_n$, since it is semisimple. Hence, the growth of the elements in the algebra when one multiplies these generators is exponential. Then one may extract the matrix entries by multiplying with a basis of $\mathcal{C}_n$ and taking traces (to get inner products with the basis, and hence essentially the entries of the matrix). The number of these traces grows exponentially, hence the number of flow polynomials of the graphs (hence the chromatic polynomials of the dual planar graphs) as a function of the number of vertices.

For concreteness, we have an explicit example to demonstrate this approach. We want the smallest dimension subalgebra possible, so it's convenient to set $Q=\phi+1 = \frac{3+\sqrt{5}}{2}$ since $\mathcal{C}_n$ then has a non-trivial trace radical generated by the Tutte relation:

For trivalent (cubic) graphs, it is convenient to use this form of the relation:

Adding this relation (which doesn't affect the value of the flow polynomial for planar graphs at $Q=\phi+1$) decreases the dimension of the algebra, and hence makes it easier to compute with.

We'll do a variation on the above strategy. Consider the
elements $A, B$ of $\mathcal{C}_3$ in this picture:

We can multiply (by stacking) $A$ and $B$ with the
graphs $e_1, e_2$, which are not elements of $\mathcal{C}_3^{\phi+1}$,
but of a related vector space $\mathcal{C}_{3,1}$ which is a module over $\mathcal{C}_3$
(really in the planar algebra), for $Q=\phi+1$ (obtained the
same way by taking graphs modulo the deletion-contraction relations).
Then we may compute $Ae_1= -\phi e_1, Ae_2=-\phi^2 e_2-\phi e_1,$
$Be_1=-\phi^2 e_2-\phi e_1, Be_2=-\phi e_2$, so the action of $A,B$
preserves the subspace spanned by $e_1,e_2$. These are represented
by the matrices:

$A=\left(\begin{array}{cc}-\phi & -\phi \\0 & -\phi^2\end{array}\right),$
$B=\left(\begin{array}{cc}-\phi^2 & 0 \\-\phi & -\phi\end{array}\right),$

Now, multiply $A, B$ together $n$ times, getting $2^n$ elements
of $\mathcal{C}_3$. Then add on $e_1, e_2$ on bottom, and their
reflections on top, to get an element of $\mathcal{C}_1$. Then
take the trace, so connect by an arc running from top to bottom,
and evaluate the flow polynomial. The graphs $A,B$ then have
a subsemigroup in $GL(2,\mathbb{R})$ which is free (since they
have distinct eigenvectors), so the
various products give distinct elements of $\mathcal{C}_3$,
and hence we get at least $2^{n/4}$ distinct coefficients when we pair
with the $e_i$s and take the trace.

Here's $ABAAB$ capped off one way:

thatin the literature. $\endgroup$ – Gerry Myerson Jun 8 '16 at 23:19