On the Weisfeiler-Leman dimension of permutation graphs

DOI10.1137/23M1575019MaRDI QIDQ6561325zbMATH OpenFDO

Authors Jin Guo, Alexander L. Gavrilyuk, Ilya Ponomarenko

Publication date 25 June 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph isomorphismcoherent configurationpermutation graphscomparability graphsWeisfeiler-Leman dimensionWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Recommendations

• The Weisfeiler-Leman dimension of planar graphs is at most 3
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• scientific article; zbMATH DE number 7561610

Cites work

• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An optimal lower bound on the number of variables for graph identification
• Capturing polynomial time using modular decomposition
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism, color refinement, and compactness
• Graphs Identified by Logics with Counting
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• On Comparability and Permutation Graphs
• On testing isomorphism of permutation graphs
• Partial orders of dimension 2
• Separability number and Schurity number of coherent configurations
• Sherali-Adams relaxations and indistinguishability in counting logics
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(1)

• On the WL-dimension of circulant graphs of prime power order

This page was built for publication: On the Weisfeiler-Leman dimension of permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6561325)