Seurat games on Stockmeyer graphs

Abstract

We define a family of vertex colouring games played over a pair of graphs or digraphs (Formula presented.) by players (Formula presented.) and (Formula presented.). These games arise from work on a longstanding open problem in algebraic logic. It is conjectured that there is a natural number (Formula presented.) such that (Formula presented.) always has a winning strategy in the game with (Formula presented.) colours whenever (Formula presented.). This is related to the reconstruction conjecture for graphs and the degree-associated reconstruction conjecture for digraphs. We show that the reconstruction conjecture implies our game conjecture with (Formula presented.) for graphs, and the same is true for the degree-associated reconstruction conjecture and our conjecture for digraphs. We show (for any (Formula presented.)) that the 2-colour game can distinguish certain nonisomorphic pairs of graphs that cannot be distinguished by the (Formula presented.) -dimensional Weisfeiler–Leman algorithm. We also show that the 2-colour game can distinguish the nonisomorphic pairs of graphs in the families defined by Stockmeyer as counterexamples to the original digraph reconstruction conjecture.