Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

DOI10.1017/9781139028868OpenAlexW2743930031MaRDI QIDQ5347096

Martin Grohe

Publication date: 22 May 2017

Full work available at URL: https://doi.org/10.1017/9781139028868

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Graph theory (05C99) Models of other mathematical theories (03C65)

Related Items (22)

Separability of Schur rings over abelian groups of odd order ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Seurat games on Stockmeyer graphs ⋮ Quantum and non-signalling graph isomorphisms ⋮ On the WL-dimension of circulant graphs of prime power order ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph isomorphism restricted by lists ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ On WL-rank and WL-dimension of some Deza circulant graphs ⋮ The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs ⋮ Choiceless Logarithmic Space ⋮ Unnamed Item ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ On the separability of cyclotomic schemes over finite fields ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs

This page was built for publication: Descriptive Complexity, Canonisation, and Definable Graph Structure Theory