Chromatic polynomial of a grid graph 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,?
 A: Wolfram Mathematica can compute chromatic polynomial for some graphs.
See http://mathworld.wolfram.com/ChromaticPolynomial.html

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 http://oeis.org/wiki/Colorings_of_grid_graphs
A: 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}. $$
A: 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.
 
