On the representation number of chessboard graphs

Abstract

The representation number of a graph is the smallest integer k such that the graph can be represented by a word in which each vertex appears exactly k times, and two distinct vertices x and y alternate in the word if and only if they are adjacent in the graph. We extend known results on the representation number for various graph classes to chessboard graphs—namely, king, queen, rook, bishop, and knight graphs. We provide a complete classification for queen graphs and partial classifications or observations for the other classes. As a consequence of our study, we obtain a characterization of all chessboard graphs that are circle graphs. Our work also leads to several interesting open problems.