King's graph explained

King's graph
Vertices:	nm
Edges:	4 nm -3 (n + m) +2
Chromatic Number:	4 when min (m,n)> 1
Chromatic Index:	8 when min (m,n)> 2
Girth:	3 when min (m,n)> 1

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an

n x m king's graph is a king's graph of an n x m chessboard.^[1] It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.^[2]

For an

n x m king's graph the total number of vertices is n m and the number of edges is 4 nm -3 (n + m) + 2 . For a square n x n king's graph this simplifies so that the total number of vertices is n ^{2} and the total number of edges is ( 2 n -2 )( 2 n -1 ) .

The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.^[3] A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.^[4]

In the drawing of a king's graph obtained from an

n x m chessboard, there are (n -1 )(m -1 ) crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment. In this way, (n -1 )(m -1 ) -4 crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every 2 x n king's graph is a planar graph. However, when both n and m are at least four, and they are not both equal to four, (n -1 )(m -1 ) -4 is the optimal number of crossings.

See also

• Knight's graph
• Queen's graph
• Rook's graph
• Bishop's graph
• Lattice graph

Notes and References

1. . Chang defines the king's graph on p. 341.
2. .
3. .
4. .