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 embedding with vertices corresponding to squares
of the chessboard has edges which overlap other edges
when drawn as straight lines, 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.
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.
-queen graphs have nice embeddings,
illustrated above. In general, the embedding with vertices corresponding to squares
of the chessboard has edges which overlap other edges
when drawn as straight lines, the only nontrivial exception being the 
-queen graph.
"Queen", 
m, n
].
-queen graph
-knight graph
-queen
graph
-queen
graph
-knight graph
-queen
graph, which is isomorphic to the tetrahedral graph 
.
, 
, and 
.
is given by
-queen graphs for 
, 3, ... are 6, 3920, ... (OEIS A158663),
with the corresponding numbers of Hamiltonian paths
given by 24, 45856, ... (OEIS A158664).
-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).
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.
Graph Coloring Problems." J. Heuristics 10,
407-413, 2004.Wagon, S. "Graph Theory Problems from Hexagonal and
Traditional Chess." College Math. J. 45, 278-287, 2014.