Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

DOI10.1007/978-3-642-40450-4_13zbMath1362.68097OpenAlexW2616240124MaRDI QIDQ2849306

Martin Grohe, Christoph Berkholz, Paul Bonsma

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://publications.rwth-aachen.de/record/689385/files/689385.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Graph isomorphism, color refinement, and compactness ⋮ Graphs Identified by Logics with Counting ⋮ On the Power of Color Refinement ⋮ Unfoldings and Coverings of Weighted Graphs ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Relational linear programming ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ Isomorphism Test for Digraphs with Weighted Edges.

Uses Software

• nauty

This page was built for publication: Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement