Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
From MaRDI portal
Publication:5009334
DOI10.1137/20M1327550zbMath1482.05235arXiv1907.02892OpenAlexW3193325593MaRDI QIDQ5009334
Frank Fuhlbrück, Oleg Verbitsky, Johannes Köbler
Publication date: 20 August 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.02892
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
On the WL-dimension of circulant graphs of prime power order ⋮ On WL-rank and WL-dimension of some Deza circulant graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Schurity and separability of quasiregular coherent configurations
- An optimal lower bound on the number of variables for graph identification
- A very hard log-space counting class
- On highly closed cellular algebras and highly closed isomorphisms
- Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
- A non-Schurian coherent configuration on 14 points exists
- Coherent configurations associated with TI-subgroups
- Graph isomorphism, color refinement, and compactness
- Finite permutation groups of rank 3
- Configurations from a Graphical Viewpoint
- Graphs Identified by Logics with Counting
- An Introduction to Incidence Geometry
- On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs
- Powers of tensors and fast matrix multiplication
- Undirected connectivity in log-space
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Distinguishing Vertices of Random Graphs
- Structure and importance of logspace-MOD class
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- On finite rigid structures
- Benchmark Graphs for Practical Graph Isomorphism
- An exponential lower bound for individualization-refinement algorithms for graph isomorphism
- On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
- Graph isomorphism in quasipolynomial time [extended abstract]
- Constructing Hard Examples for Graph Isomorphism
- Fast matrix rank algorithms and applications
- On Hypergraph and Graph Isomorphism with Bounded Color Classes
- On quasi-thin association schemes
- On the Weisfeiler-Leman dimension of fractional packing
- Linear spaces with few lines
