Chromatic polynomial of a grid graph

Question

I have the following graph with $nm$ vertices:

1 --- 2 --- 3 --- (n)
|     |     |
4 --- 5 --- 6 --- (n)
|     |     |
7 --- 8 --- 9 --- (n)
|     |     | 
|     |     |
(m)   (m)   (m)

In other words, this is a graph of a grid with $m$ rows and $n$ columns. How can I determine the chromatic polynomial of this graph? Say, for $n=4$ and $m=4$? Is there a way to form a general formula for such a graph,?

Answer 1

This is an open problem by Read and Tutte . You are essentially asking for the chromatic polynomial of the grid graph (the vertices of degree $1$ do not matter.)See the attached picture from Read R.C. and W.T. Tutte. Chromatic polynomials. In: L.W. Beineke and R.J. Wilson, Selected Topics in Graph Theory, volume 3, pages 15--42.

Also here are some slides from a not so old talk in which it was said that this is still open.

Answer 2

Wolfram Mathematica can compute chromatic polynomial for some graphs, as explained in this web page.

The chromatic polynomial of a graph g in the variable z can be determined using ChromaticPolynomial[g, z] in the Mathematica package Combinatorica . Precomputed chromatic polynomials for many named graphs can be obtained using GraphData[graph, "ChromaticPolynomial"][z].

Mathematica has precomputed polynomials for grid graphs up to $n<5$ & $m<5$. I tried to compute ChromaticPolynomial[GridGraph[3, 6], z] but it didn't finished yet after an hour.

See also this web page.

Answer 3

Let $\chi_{m,n}(q)$ denote the chromatic polynomial of an $m\times n$ grid graph. An application of the transfer-matrix method shows that for fixed $m$, the generating function $\sum_{n\geq 1}\chi_{m,n}(q)x^n$ is a rational function of $q$ and $x$. For $m=3$ we get $$ \sum_{n\geq 1}\chi_{3,n}(q)x^n = \frac{q(1-q)(1-q+(1-3q+q^2)x)x} {1+(10-11q+5q^2-q^3)x+(11-24q+19q^2-7q^3+q^4)x^2}. $$ It is also easy to see directly that $$ \chi_{2,n}(q) = q(q-1)(q^2-3q+3)^{n-1}. $$