Seurat games on Stockmeyer graphs

DOI10.1002/jgt.22741zbMath1522.05303arXiv2008.01327MaRDI QIDQ6056811

Robert Egrot, Robin Hirschl

Publication date: 4 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.01327

zbMATH Keywords

reconstruction conjectureWeisfeiler-Leman algorithmgraph isomorphismscolour refinementStockmeyer graphstally spectra

Mathematics Subject Classification ID

Games involving graphs (91A43) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (2)

FIRST-ORDER AXIOMATISATIONS OF REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS OF UNBOUNDED QUANTIFIER DEPTH ⋮ Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relation algebras by games
• Elements of finite model theory.
• Relation algebras
• N-reconstructibility of non-reconstructible digraphs
• A census of non-reconstructable digraphs. I: Six related families
• On a new digraph reconstruction conjecture
• The origin of relation algebras in the development and axiomatization of the calculus of relations
• An optimal lower bound on the number of variables for graph identification
• On representable relation algebras
• The representation of relational algebras
• Topics in Graph Automorphisms and Reconstruction
• The falsity of the reconstruction conjecture for tournaments
• Nonfinite axiomatizability results for cylindric and relation algebras
• FIRST-ORDER AXIOMATISATIONS OF REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS OF UNBOUNDED QUANTIFIER DEPTH
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Canonical varieties with no canonical axiomatisation
• Algebraic Logic, Where Does it Stand Today?
• Ulam's Conjecture and Graph Reconstructions
• Relation algebras from cylindric algebras. II

This page was built for publication: Seurat games on Stockmeyer graphs