3
$\begingroup$

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

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

3 Answers 3

Reset to default
12
$\begingroup$

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.

enter image description here

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Jan 18, 2014 at 22:00
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .