This site is supported by donations to The OEIS Foundation.

Colorings of grid graphs

From OeisWiki
Jump to: navigation, search


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


3-by-4 grid graph
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)[1](3-dimensional graphs)[2] 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]

Notes