The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3

DOI10.1145/3333003zbMath1483.05048arXiv1708.07354OpenAlexW2991150483WikidataQ126671768 ScholiaQ126671768MaRDI QIDQ5215472

Pascal Schweitzer, Sandra Kiefer, Ilya Nikolaevich Ponomarenko

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsisomorphism testingWeisfeiler-Leman algorithmfirst-order logic with counting

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

Separability of Schur rings over abelian groups of odd order ⋮ On polyhedral graphs and their complements ⋮ On WL-rank of Deza Cayley graphs ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ 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: The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3