# 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,?

• I'm a bit confused. Do the $(n)$'s and $(m)$'s represent vertices? Jan 18, 2014 at 19:38
• @Casteels yes. It means that it can have n * m vertices. Basically its a grid. Jan 18, 2014 at 19:48
• Here's something to read: arxiv.org/abs/1103.6206 Jan 18, 2014 at 20:02
• @MatthewConroy: Reading it now. Thanks. :) Jan 18, 2014 at 20:15
• Couldnt get much of it. :( Jan 18, 2014 at 20:23

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.

• The picture in the post suggests that the solution for general $n$ and $m$ is not known. In particular, some well known mathematicians did not know how to solve it. Jan 18, 2014 at 22:00

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.

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}.$$