On the representation number of chessboard graphs

Tools

Kitaev, Sergey and Pyatkin, Artem (2026) On the representation number of chessboard graphs. Acta Informatica, 63 (4). 33. (https://doi.org/10.1007/s00236-026-00547-w)

[thumbnail of Kitaev-Pyatkin-AI-2026-On-the-representation-number-of-chessboard]
Preview
 Text. Filename: Kitaev-Pyatkin-AI-2026-On-the-representation-number-of-chessboard.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (408kB)| Preview

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)