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.
| Type: | Article |
|---|---|
| Title: | Seurat games on Stockmeyer graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/jgt.22741 |
| Publisher version: | https://doi.org10.1002/jgt.22741 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | colour refinement, graph isomorphisms, reconstruction conjecture, Stockmeyer graphs, tally spectra, Weisfeiler-Leman algorithm |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10136455 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
