The Weisfeiler-Leman dimension of distance-hereditary graphs

DOI10.1007/s00373-023-02683-3zbMath1525.05133arXiv2005.11766OpenAlexW3027991412MaRDI QIDQ6166669

Alexander L. Gavrilyuk, Roman Nedela, Ilya Nikolaevich Ponomarenko

Publication date: 3 August 2023

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

distance-hereditary graphgraph isomorphism problemWeisfeiler-Leman algorithmWeisfeiler-Leman dimension

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Distance-hereditary graphs
• An optimal lower bound on the number of variables for graph identification
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
• Graph isomorphism, color refinement, and compactness
• Rank-width and vertex-minors
• Tensor products of coherent configurations
• Graphs Identified by Logics with Counting
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
• Canonisation and Definability for Graphs of Bounded Rank Width

This page was built for publication: The Weisfeiler-Leman dimension of distance-hereditary graphs