On the power of color refinement
DOI10.1007/978-3-319-22177-9_26zbMATH Open1436.05101OpenAlexW2287453393MaRDI QIDQ2947892FDOQ2947892
Gaurav Rattan, Johannes Köbler, Vikraman Arvind, Oleg Verbitsky
Publication date: 29 September 2015
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-22177-9_26
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Title not available (Why is that?)
- Graph isomorphism and theorems of Birkhoff type
- Title not available (Why is that?)
- Decomposition of graphical sequences and unigraphs
- Random Graph Isomorphism
- Recognition of unigraphs through superposition of graphs
- Compact graphs and equitable partitions
- Pairs of sequences with a unique realization by bipartite graphs
- Fractional isomorphism of graphs
- Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
- Dimension Reduction via Colour Refinement
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- Title not available (Why is that?)
- Simple separable graphs
- Graphs Identified by Logics with Counting
- On Tinhofer’s Linear Programming Approach to Isomorphism Testing
- Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
Cited In (4)
This page was built for publication: On the power of color refinement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947892)
