Egrot R.Hirsch R.Mahidol University2023-06-222023-06-222022-02-01Journal of Graph Theory Vol.99 No.2 (2022) , 278-31103649024https://repository.li.mahidol.ac.th/handle/123456789/87537We 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.MathematicsArticleSCOPUS10.1002/jgt.227412-s2.0-8511535015410970118