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)

Full work available at URL https://doi.org/10.1137/23M1575019

zbMATH Keywords

coherent configurationcomparability graphsgraph isomorphismpermutation graphsWeisfeiler-Leman algorithmWeisfeiler-Leman dimension

Mathematics Subject Classification ID

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

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

• 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)
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism, color refinement, and compactness
• Graphs Identified by Logics with Counting
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• 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)