On the Weisfeiler-Leman dimension of permutation graphs
DOI10.1137/23m1575019zbMATH Open1542.0512MaRDI QIDQ6561325
Ilya Nikolaevich Ponomarenko, Alexander L. Gavrilyuk, Jin Guo
Publication date: 25 June 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
comparability graphspermutation graphscoherent configurationgraph isomorphismWeisfeiler-Leman algorithmWeisfeiler-Leman dimension
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Cites Work
- Unnamed Item
- Unnamed Item
- 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)
- Algorithmic graph theory and perfect graphs
- Separability number and Schurity number of coherent configurations
- The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
- Graph isomorphism, color refinement, and compactness
- Sherali--Adams Relaxations and Indistinguishability in Counting Logics
- On Comparability and Permutation Graphs
- On testing isomorphism of permutation graphs
- Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
- Graphs Identified by Logics with Counting
- 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
- Graph isomorphism in quasipolynomial time [extended abstract]
- Transitiv orientierbare Graphen
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Partial orders of dimension 2
- The Weisfeiler-Leman dimension of distance-hereditary graphs
This page was built for publication: On the Weisfeiler-Leman dimension of permutation graphs
