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.Cockayne, E. J. and Hedetniemi, S. T. "On the Diagonal Queens Domination Problem." J. Combin. Th. Ser. A42, 137-139, 1986.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. "The Eight Queens Problem." 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." 25 Jun 2016. https://arxiv.org/abs/1606.07918.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
]. 
minus a cycle graph 
-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.