This site is supported by donations to The OEIS Foundation.

Colorings of grid graphs

From OeisWiki
(Redirected from Colorings of square grid graphs)
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 2 3 4 5 6 7 8 9 10 A000027
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

  1. ↑ To do: rectangular graphs.
  2. ↑ To do: 3-dimensional graphs.
  3. ↑ Peter Tittmann, Polynomials of nxn Grid Graphs [Broken link].
  4. ↑ Bedini A., Jacobsen J. (2010), A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings.
Retrieved from "https://oeis.org/w/index.php?title=Colorings_of_grid_graphs&oldid=1647813#Colorings_of_square_grid_graphs"