King's graph

A king's graph is a graph theory construction that represents every legal move of a king on a chessboard: each vertex stands for one square of an n by m board, and an edge connects two vertices whenever a king could move directly between those squares in a single step, horizontally, vertically or diagonally. An n by m king's graph has nm vertices and follows the edge-count formula four nm minus three times the sum of n and m, plus two. The graph can also be described as the strong product of two path graphs, or built by treating each board square as a vertex of a map graph and connecting squares that touch along an edge or at a corner. Its girth is three, and its chromatic number is four whenever both board dimensions exceed one. Because the neighborhood of each vertex mirrors the Moore neighborhood used in cellular automata, king's graphs also appear in that field. Two by n king's graphs are planar, and the structure sits alongside related graphs built from the moves of other chess pieces, including the knight's, queen's, rook's and bishop's graphs.