论文标题
Seurat游戏在Stockmeyer图上
Seurat games on Stockmeyer graphs
论文作者
论文摘要
我们定义了一个在$ \ forall $和$ \的$ \ for的$ \ for的$ \ $ \的家族中，$ \ forall $ and $ \ coplast $。这些游戏来自代数逻辑中长期存在的开放问题的工作。据推测，有一个自然的$ n $，因此每当$ g \ g \ not \ cong h $时，$ \ forall $总是在游戏中具有成功的策略。这与图形的重建猜想以及与挖掘的程度相关的重建猜想有关。我们表明，重建猜想意味着我们的游戏猜想是图形的$ n = 3 $，而与学位相关的重建猜想和我们对Digraphs的猜想也是如此。我们（对于任何$ k <ω$）显示了2彩游戏可以区分某些无法通过$ k $ dimensional weisfeiler-leman算法来区分的图形对图。我们还表明，2彩游戏可以区分斯托克梅尔定义为原始Digraph重建猜想的家族中的非晶格对。
We define a family of vertex colouring games played over a pair of graphs or digraphs $(G,H)$ by players $\forall$ and $\exists$. 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 $\forall$ always has a winning strategy in the game with $n$ colours whenever $G\not\cong 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.
