On the Weisfeiler-Leman dimension of permutation graphs

DOI10.1137/23M1575019zbMATH Open1542.0512MaRDI QIDQ6561325FDOQ6561325

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)

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

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)

Cites Work

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