Seurat games on Stockmeyer graphs
Issued Date
2022-02-01
Resource Type
ISSN
03649024
eISSN
10970118
Scopus ID
2-s2.0-85115350154
Journal Title
Journal of Graph Theory
Volume
99
Issue
2
Start Page
278
End Page
311
Rights Holder(s)
SCOPUS
Bibliographic Citation
Journal of Graph Theory Vol.99 No.2 (2022) , 278-311
Suggested Citation
Egrot R., Hirsch R. Seurat games on Stockmeyer graphs. Journal of Graph Theory Vol.99 No.2 (2022) , 278-311. 311. doi:10.1002/jgt.22741 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/87537
Title
Seurat games on Stockmeyer graphs
Author's Affiliation
Other Contributor(s)
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.