On Weisfeiler-Leman invariance: subgraph counts and related graph properties
From MaRDI portal
Publication:5918849
DOI10.1016/j.jcss.2020.04.003zbMath1450.05056arXiv1811.04801OpenAlexW2965757697MaRDI QIDQ5918849
V. Arvind, Oleg Verbitsky, Frank Fuhlbrück, Johannes Köbler
Publication date: 9 June 2020
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.04801
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (4)
Local WL invariance and hidden shades of regularity ⋮ On the expressive power of linear algebra on graphs ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- On the power of combinatorial and spectral invariants
- On the parameterized complexity of multiple-interval graph problems
- Affine systems of equations and counting infinitary logic
- On matching coefficients
- An optimal lower bound on the number of variables for graph identification
- A restricted second order logic for finite structures
- Fractional isomorphism of graphs
- Pebble games and cospectral graphs
- Logical hierarchies in PTIME
- The matching polynomial of a distance-regular graph
- Graph isomorphism, color refinement, and compactness
- Practical graph isomorphism. II.
- Finite permutation groups of rank 3
- Graphs Identified by Logics with Counting
- On recognizing graphs by numbers of homomorphisms
- Solving Linear Programs without Breaking Abstractions
- On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs
- Random Graph Isomorphism
- The Structure and Function of Complex Networks
- On Hanf-equivalence and the number of embeddings of small induced subgraphs
- Paths in graphs
- Homomorphisms are a good basis for counting small subgraphs
- Lov\'asz Meets Weisfeiler and Leman
- On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
- Graph isomorphism in quasipolynomial time [extended abstract]
- Fixed-point definability and polynomial time on graphs with excluded minors
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
This page was built for publication: On Weisfeiler-Leman invariance: subgraph counts and related graph properties
