Egrot, R; Hirsch, R; (2022) Seurat games on Stockmeyer graphs. Journal of Graph Theory , 99 (2) pp. 278-311. 10.1002/jgt.22741.

Preview

Text Seurat_JGT_Resubmission.pdf - Accepted Version Download (507kB) | Preview

Abstract

We define a family of vertex colouring games played over a pair of graphs or digraphs (G, H) by players ∀ and ∃. These games arise from work on a longstanding open problem in algebraic logic. It is conjectured that there is a natural number n such that ∀ always has a winning strategy in the game with n colours whenever G 6∼= H. 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 n = 3 for graphs, and the same is true for the degree-associated reconstruction conjecture and our conjecture for digraphs. We show (for any k < ω) that the 2-colour game can distinguish certain non-isomorphic pairs of graphs that cannot be distinguished by the k-dimensional Weisfeiler-Leman algorithm. We also show that the 2-colour game can distinguish the non-isomorphic pairs of graphs in the families defined by Stockmeyer as counterexamples to the original digraph reconstruction conjecture.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item