Graph isomorphism, color refinement, and compactness
From MaRDI portal
Publication:2410688
DOI10.1007/s00037-016-0147-6zbMath1379.05080arXiv1502.01255OpenAlexW2119446222MaRDI QIDQ2410688
Gaurav Rattan, V. Arvind, Johannes Köbler, Oleg Verbitsky
Publication date: 18 October 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.01255
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
On WL-rank of Deza Cayley graphs, On Tinhofer’s Linear Programming Approach to Isomorphism Testing, The Weisfeiler-Leman dimension of distance-hereditary graphs, On pseudofrobenius imprimitive association schemes, Unnamed Item, The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, On WL-rank and WL-dimension of some Deza circulant graphs, Approximate lumpability for Markovian agent-based models using local symmetries, Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on certain subpolytopes of the assignment polytope associated with circulant graphs
- Compact graphs and equitable partitions
- Graph isomorphism and theorems of Birkhoff type
- Some applications of doubly stochastic matrices
- Strong tree-cographs are Birkhoff graphs
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- Finite common coverings of graphs
- A note on compact graphs
- An optimal lower bound on the number of variables for graph identification
- Pairs of sequences with a unique realization by bipartite graphs
- Simple separable graphs
- Compact cellular algebras and permutation groups
- Fractional isomorphism of graphs
- Decomposition of graphical sequences and unigraphs
- Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
- Equivalence in finite-variable logics is complete for polynomial time
- Sherali-Adams relaxations of graph isomorphism polytopes
- On compact graphs
- Sherali--Adams Relaxations and Indistinguishability in Counting Logics
- Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
- Recognition of Unigraphs through Superposition of Graphs
- Dimension Reduction via Colour Refinement
- Graphs Identified by Logics with Counting
- On Tinhofer’s Linear Programming Approach to Isomorphism Testing
- On the Power of Color Refinement
- PEBBLE GAMES AND LINEAR EQUATIONS
- Random Graph Isomorphism
- Congruent Graphs and the Connectivity of Graphs
- Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
- Enumeration of Schur Rings over the Group A 5
