The queen graph is a graph with vertices in which each vertex represents a square in an chessboard,
and each edge corresponds to a legal move by a queen. The -queen graphs have nice embeddings, illustrated above.
In general, the default embedding with vertices corresponding to squares of the chessboard has degenerate superposed edges, the only
nontrivial exception being the -queen graph.
Since each row and column of an -queen graph is an -clique, these graphs have chromatic
number at least .
And in fact, when ,
it can be shown that
colors suffice. In fact, the chromatic numbers
for , 3, ... are 4, 5, 5, 5, 7, 7, 9, 10,
11, 11, 12, 13, ... (OEIS A088202).
Queen graphs
are class 1 when at least one of or
is even (J. DeVincentis and S. Wagon, pers. comm., Nov. 13-14, 2011)
and when
and are both odd with (S. Wagon, pers. comm., Dec. 9, 2015).
On the other hand, a queen graph with odd and is trivially class
2 (S. Wagon, pers. comm., Dec. 9, 2015), which leaves only the case
of odd
with open.
Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc.
Math.163, 47-66, 1997.Chandra, A. K. "Independent
Permutations, as Related to a Problem of Moser and a Theorem of Pólya."
J. Combin. Th. Ser. A16, 111-120, 1974.Chvátal,
V. "Coloring the Queens Graph." http://users.encs.concordia.ca/~chvatal/queengraphs.html.Finozhenok,
D. and Weakley, W. D. "An Improved Lower Bound for Domination Numbers of
the Queen's Graph." Australasian J. Combin.37, 295-300, 2007.Fricke,
G. H.; Hedemiemi, S. M.; Hedetniemi, S. T.; McRae. A. A.; Wallis,
C. K.; Jacobsen, M. S.; Martinand, H. W.; abd Weakley, W. D.
"Combinatorial Problems on Chessboards: A Brief Survey." In Graph Theory,
Combinatoricsand Applications, Vol. I, Prec. Seventh QuadrennialConf.on the
Theory and Application sof Graphs (Ed. Alavi and Schwenk). Western Michigan
University, 1995.Gardner, M. The
Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University
of Chicago Press, pp. 116-118 and 124-126, 1984.Gardner, M. The
Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago
University Press, p. 191, 1991.Gosset, T. Mess. Math.44,
48, 1914.Hwang, F. K. and Lih, K. W. "Latin Squares and
Superqueens." J. Combin. Th. Ser. A34, 110-114, 1983.Jarnicki,
W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured,
of Keller, Mycielski, and Queen Graphs." To appear in Ars Math. Comtemp. 2017.Karavaev,
A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Östergård,
P. R. J. and Weakley, W. D. "Values of Domination Numbers of
the Queen's Graph." Elec. J. Combin.8, Issue 1, No. R29,
2001. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r29.Perepechko,
S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an
Undirected Graph. Explicit Formulae in Case of Small Lengths."Sloane,
N. J. A. Sequence A088202, A158663,
and A158664 in "The On-Line Encyclopedia
of Integer Sequences."Shapiro, H. D. "Generalized Latin
Squares on the Torus," Disc. Math.24, 63-77, 1978.Vasquez,
M. "New Results on the Queens Graph Coloring Problems." J. Heuristics10,
407-413, 2004.Wagon, S. "Graph Theory Problems from Hexagonal and
Traditional Chess." College Math. J.45, 278-287, 2014.