A graph $G$ is a queens graph if the vertices of $G$ can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position. We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. % is not representable in the same way. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem. We also prove constructively that any finite subgraph of the grid or the hexagonal grid is a queens graph.
|Publication status||Published - 2004|
|Event||Graph Theory 2004: a conference in memory of Claude Berge - Paris|
Duration: 1 Jan 2004 → …
|Conference||Graph Theory 2004: a conference in memory of Claude Berge|
|Period||01/01/2004 → …|