Queen's graph

Queen's graph
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h In an ${\displaystyle 8\times 8}$ queen's graph, each square of the chessboard above is a vertex. There is an edge between any two vertices that a queen could move between; as an example, the vertices adjacent to d4 are marked with a white dot (i.e. there is an edge from d4 to each marked vertex).
Vertices	${\displaystyle mn}$
Chromatic number	n if ${\displaystyle m=n\equiv 1,5{\pmod {6}}}$
Properties	Biconnected, Hamiltonian
Table of graphs and parameters

In mathematics, a queen's graph is an undirected graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a legal move the queen can make, that is, a horizontal, vertical or diagonal move by any number of squares. If the chessboard has dimensions ${\displaystyle m\times n}$, then the induced graph is called the ${\displaystyle m\times n}$ queen's graph.

Independent sets of the graphs correspond to placements of multiple queens where no two queens are attacking each other. They are studied in the eight queens puzzle, where eight non-attacking queens are placed on a standard ${\displaystyle 8\times 8}$ chessboard. Dominating sets represent arrangements of queens where every square is attacked or occupied by a queen; five queens, but no fewer, can dominate the ${\displaystyle 8\times 8}$ chessboard.

Colourings of the graphs represent ways to colour each square so that a queen cannot move between any two squares of the same colour; at least n colours are needed for an ${\displaystyle n\times n}$ chessboard, but 9 colours are needed for the ${\displaystyle 8\times 8}$ board.