This site is supported by donations to The OEIS Foundation.

# Colorings of grid graphs

(Redirected from Colorings of square grid graphs)
Jump to: navigation, search

This article page is a stub, please help by expanding it.

An
 n  ×  m
grid graph is a graph whose vertices can be arranged in a regular two-dimensional
 n  ×  m
mesh such that there is an edge between every pair of horizontally or vertically adjacent vertices. This article is concerned with the number of
 q
-colorings of such graphs, i.e. the number of ways to assign one of
 q
colors to each vertex such that no two adjacent vertices have the same color. It is known that for any graph
 G
, the number of
 q
-colorings of
 G
is a polynomial in
 q
, a so-called chromatic polynomial of
 G
. The degree of the chromatic polynomial is equal to the number of vertices in the graph.

## Colorings of square grid graphs

Chromatic polynomials have been computed for
 n  ×  n
square grid graphs(rectangular graphs)(3-dimensional graphs) with
 n = 1, ..., 13, 14, 16, 18.

Table of number of
 q
-colorings for
 n  ×  n
square grid graph

 n \ q
1 2 3 4 5 6 7 8 9 10 A-numbers
1 1 1 1 1 1 1 1 1 1 1 A000012
2 0 2 18 84 260 630 1302 2408 4104 6570 A091940;
 2  ×
A027441
 (q  −  1), q   ≥   1
;
 (q  −  1)  ×  q  ×
A002061
 (q  −  1), q   ≥   1
;
 2  ×
A000217
 (q  −  1)  ×
A002061
 (q  −  1), q   ≥   1
3 0 2 246 9612 142820 1166910 6464682 27350456 95004072 283982490
 2  ×
A068239
 (q), q   ≥   2
4 0 2 7812 6000732 828850160 38128724910 856858754052 11722360851992 111647093496192 807567269568570
 2  ×
A068240
 (q), q   ≥   2
5 0 2 580986 20442892764 50820390410180 21977869327169310 3031776844080257742 1.9e+20 6.66e+21 1.51e+23
 2  ×
A068241
 (q), q   ≥   2
6 0 2 101596896 380053267505964 3.29e+19 2.23e+23 2.86e+26 1.16e+29 2.02e+31 1.86e+33
 2  ×
A068242
 (q), q   ≥   2
7 0 2 41869995708 3.86e+19 2.25e+26 4.01e+31 7.22e+35 2.66e+39 3.1e+42 1.51e+45
 2  ×
A068243
 (q), q   ≥   2
8 0 2 40724629633188 2.13e+25 1.63e+34 1.27e+41 4.86e+46 2.32e+51 2.42e+55 8.02e+58
 2  ×
A??????
 (q), q   ≥   2
9 0 2 93574975249028022 6.45e+31 1.24e+43 7.08e+51 8.73e+58 7.59e+64 9.59e+69 2.81e+74
 2  ×
A??????
 (q), q   ≥   2
10 0 2 5.08e+20 1.06e+39 1e+53 6.97e+63 4.19e+72 9.4e+79 1.93e+86 6.48e+91
 2  ×
A??????
 (q), q   ≥   2
11 0 2 6.53e+24 9.57e+46 8.57e+63 1.21e+77 5.36e+87 4.39e+96 1.97e+104 9.84e+110
 2  ×
A??????
 (q), q   ≥   2
12 0 2 1.98e+29 4.7e+55 7.72e+75 3.71e+91 1.83e+104 7.73e+114 1.02e+124 9.82e+131
 2  ×
A??????
 (q), q   ≥   2
13 0 2 1.43e+34 1.26e+65 7.35e+88 2.01e+107 1.67e+122 5.14e+134 2.69e+145 6.45e+154
 2  ×
A??????
 (q), q   ≥   2
A000007;
 (0  ×  1)  ×
whatever
 (n),

 n   ≥   2
A040000;
 (1  ×  2)  ×
A000012
 (n),

 n   ≥   2
 (2  ×  3)  ×

A207993
 (n),

 n   ≥   2
 (3  ×  4)  ×

A??????
 (n),

 n   ≥   2
 (4  ×  5)  ×

A??????
 (n),

 n   ≥   2
 (5  ×  6)  ×

A??????
 (n),

 n   ≥   2
 (6  ×  7)  ×

A??????
 (n),

 n   ≥   2
 (7  ×  8)  ×

A??????
 (n),

 n   ≥   2
 (8  ×  9)  ×

A??????
 (n),

 n   ≥   2
 (9  ×  10)  ×

A??????
 (n),

 n   ≥   2

A207993
 1 2  ×  3
times number of
 3
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {3, 41, 1302, 96831, 16932816, 6978332618, 6787438272198, 15595829208171337, 84713253582265127190, 1088296274542436098185362, 33079232010276428576508643620, 2379573338713223879592059518246838, ...}
A??????
 1 3  ×  4
times number of
 4
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {7, 801, 500061, 1703574397, 31671105625497, ...}
A??????
 1 4  ×  5
times number of
 5
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {13, 7141, 41442508, 2541019520509, ...}
A??????
 1 5  ×  6
times number of
 6
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {21, 38897, 1270957497, 732595644238977, ...}
A??????
 1 6  ×  7
times number of
 7
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {31, 153921, 20401398906, 72185162954291851, ...}
A??????
 1 7  ×  8
times number of
 8
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {43, 488401, 209327872357, ...}
A??????
 1 8  ×  9
times number of
 9
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {57, 1319501, 1550654076336, ...}
A??????
 1 9  ×  10
times number of
 10
-colorings of
 n  ×  n
square grid graph,
 n   ≥   2
.
 {73, 3155361, 8972969661873, ...}

### Examples

#### Example: number of q-colorings of a 2 x 2 grid graph

##### Example: number of 3-colorings of a 2 x 2 grid graph
Since the number of
 2
colorings of a
 2  ×  2
grid graph is
 2
, and there are
 3
ways of choosing
 2
colors out of
 3
, we get the following
 6
ways:
```R - B   B - R   R - G   G - R   G - B   B - G
|   |   |   |   |   |   |   |   |   |   |   |        (a)
B - R   R - B   G - R   R - G   B - G   G - B
```
Replacing the top left color in (a) by the unused third color begets
 6
more ways:
```G - B   G - R   B - G   B - R   R - B   R - G
|   |   |   |   |   |   |   |   |   |   |   |        (b)
B - R   R - B   G - R   R - G   B - G   G - B
```
Replacing the top right color in (a) by the unused third color begets
 6
more ways:
```R - G   B - G   R - B   G - B   G - R   B - R
|   |   |   |   |   |   |   |   |   |   |   |        (c)
B - R   R - B   G - R   R - G   B - G   G - B
```

Replacing the bottom right color in (a) by the unused third color begets the same colorings as (b):

```R - B   B - R   R - G   G - R   G - B   B - G
|   |   |   |   |   |   |   |   |   |   |   |        (b bis)
B - G   R - G   G - B   R - B   B - R   G - R
```

Replacing the bottom left color in (a) by the unused third color begets the same colorings as (c):

```R - B   B - R   R - G   G - R   G - B   B - G
|   |   |   |   |   |   |   |   |   |   |   |        (c bis)
G - R   G - B   B - R   B - G   R - G   R - B
```
Thus, there are
 18 = 6 + 12
distinct
 3
-colorings of a
 2  ×  2
grid graph.

#### Example: number of q-colorings of a 3 x 3 grid graph

##### Example: number of 3-colorings of a 3 x 3 grid graph
Since the number of
 2
colorings of a
 3  ×  3
grid graph is
 2
, and there are
 3
ways of choosing
 2
colors out of
 3
, we get the following
 6
ways:
```R - B - R    B - R - B    R - G - R    G - R - G    G - B - G    B - G - B
|   |   |    |   |   |    |   |   |    |   |   |    |   |   |    |   |   |
B - R - B    R - B - R    G - R - G    R - G - R    B - G - B    G - B - G        (a)
|   |   |    |   |   |    |   |   |    |   |   |    |   |   |    |   |   |
R - B - R    B - R - B    R - G - R    G - R - G    G - B - G    B - G - B
```

Now, in (a), the unused color is goes in

(...)
Thus, there are
 246 = 6 + 240
distinct
 3
-colorings of a
 3  ×  3
grid graph.

#### Example: number of q-colorings of a 4 x 4 grid graph

##### Example: number of 3-colorings of a 4 x 4 grid graph
Since the number of
 2
colorings of a
 4  ×  4
grid graph is
 2
, and there are
 3
ways of choosing
 2
colors out of
 3
, we get the following
 6
ways:
(...)

Now, in (a), the unused color is goes in

(...)
Thus, there are
 7812 = 6 + 7806
distinct
 3
-colorings of a
 4  ×  4
grid graph.

## Mathematica

For small graphs, this Mathematica command can be used to compute the chromatic polynomial of a
 n  ×  m
grid graph:
```<<DiscreteMath`Combinatorica`
ChromaticPolynomial[GridGraph[n, m], q]
```