No label defined (Q3839720)

Any set of squares from an ordinary rectangular board of any dimension is called a ``chessboard''. It plays a role in the theory of rook polynomials and in the case of two dimensions it can be defined by a set of ordered pairs of positive integers. The first coordinate of each such pair denotes a row number and the second a column number. The graph \(G\) of the board \(B\) is achieved by letting squares be vertices and by stipulating that two squares are adjacent if they agree in either coordinate. With the help of this concept the first characterization of bipartite graphs is given by Theorem 1: For a graph \(G\) the following are equivalent: (1) There is a board \(B\) such that \(G\) is the graph of \(B\). (2) There is a bipartite graph \(H\) such that \(G\) is the line graph of \(H\). For the second characterization, the authors use results of Beineke about line graphs of graphs which contain none of nine subgraphs as induced subgraphs (namely \(K_{1,3}\) and eight others each of which includes \(K_4-e\) as an induced subgraph). So they receive Theorem 2: For a graph \(G\) the following are equivalent: (1) \(G\) is a line graph of a bipartite graph \(H\). (2) \(G\) contains no induced subgraph isomorphic to any of the following: \(K_{1,3}\), \(K_4-e\), and \(C_{2k+1}\) for \(k\geq 2\). This result is extended to Theorem 4: Let \(G\) be an \(n\)-dimensional chessboard. Then \(G\) contains none of the following as induced graphs: \(K_{1,n+1}\), \(K_4-e\), \(K_{2,3}\), \(C_5\). Here \(G\) is called an \(n\)-dimensional chessboard, if it is a set of ordered \(n\)-tuples of nonnegative integers, with two \(n\)-tuples considered adjacent if they agree in \(n-1\) coordinates.