(Redirected from Colorings of square grid graphs)
There are no approved revisions of this page, so it may
not have been
reviewed.
This article page is a stub, please help by expanding it.
An
grid graph is a graph whose vertices can be arranged in a regular two-dimensional
mesh such that there is an edge between every pair of horizontally or vertically adjacent vertices.
This article is concerned with the number of
-
colorings of such graphs, i.e. the number of ways to assign one of
colors to each vertex such that no two adjacent vertices have the same color.
It is known that for any graph
, the number of
-colorings of
is a polynomial in
, a so-called
chromatic polynomial of
. 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
square grid graphs (rectangular graphs) [1] (3-dimensional graphs) [2] with
n = 1, ..., 13, 14, 16, 18. |
Table of number of -colorings for square grid graph
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
A-numbers
|
1
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10
|
A000027
|
2
|
0 |
2 |
18 |
84 |
260 |
630 |
1302 |
2408 |
4104 |
6570
|
A091940; A027441 ; A002061 ; A000217 A002061
|
3
|
0 |
2 |
246 |
9612 |
142820 |
1166910 |
6464682 |
27350456 |
95004072 |
283982490
|
A068239
|
4
|
0 |
2 |
7812 |
6000732 |
828850160 |
38128724910 |
856858754052 |
11722360851992 |
111647093496192 |
807567269568570
|
A068240
|
5
|
0 |
2 |
580986 |
20442892764 |
50820390410180 |
21977869327169310 |
3031776844080257742 |
1.9e+20 |
6.66e+21 |
1.51e+23
|
A068241
|
6
|
0 |
2 |
101596896 |
380053267505964 |
3.29e+19 |
2.23e+23 |
2.86e+26 |
1.16e+29 |
2.02e+31 |
1.86e+33
|
A068242
|
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
|
A068243
|
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
|
A??????
|
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
|
A??????
|
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
|
A??????
|
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
|
A??????
|
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
|
A??????
|
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
|
A??????
|
|
A000007; whatever
|
A040000; A000012
|
A207993
|
A??????
|
A??????
|
A??????
|
A??????
|
A??????
|
A??????
|
A??????
|
|
A207993 times number of
-colorings of
square grid graph,
.
-
{3, 41, 1302, 96831, 16932816, 6978332618, 6787438272198, 15595829208171337, 84713253582265127190, 1088296274542436098185362, 33079232010276428576508643620, 2379573338713223879592059518246838, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{7, 801, 500061, 1703574397, 31671105625497, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{13, 7141, 41442508, 2541019520509, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{21, 38897, 1270957497, 732595644238977, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{31, 153921, 20401398906, 72185162954291851, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{43, 488401, 209327872357, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{57, 1319501, 1550654076336, ...} |
A??????
times number of
-colorings of
square grid graph,
.
-
{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
colorings of a
grid graph is
, and there are
ways of choosing
colors out of
, we get the following
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
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
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
distinct
-colorings of a
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
colorings of a
grid graph is
, and there are
ways of choosing
colors out of
, we get the following
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
distinct
-colorings of a
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
colorings of a
grid graph is
, and there are
ways of choosing
colors out of
, we get the following
ways:
- (...)
Now, in (a), the unused color is goes in
- (...)
Thus, there are
distinct
-colorings of a
grid graph.
Mathematica
For small graphs, this Mathematica command can be used to compute the chromatic polynomial of a
grid graph:
<<DiscreteMath`Combinatorica`
ChromaticPolynomial[GridGraph[n, m], q]
Notes