The iteration number of colour refinement
From MaRDI portal
Cites work
- A note on compact graphs
- An optimal lower bound on the number of variables for graph identification
- Canonisation and definability for graphs of bounded rank width
- Compact graphs and equitable partitions
- Dimension reduction via colour refinement
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Fixed-point definability and polynomial time on graphs with excluded minors
- Fractional isomorphism of graphs
- From Invariants to Canonization in Parallel
- Graph isomorphism, color refinement, and compactness
- Graphs identified by logics with counting
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 1754602 (Why is no real title available?)
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- On the combinatorial power of the Weisfeiler-Lehman algorithm
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
- Practical graph isomorphism. II.
- Random Graph Isomorphism
- Testing Graph Isomorphism in Parallel by Playing a Game
- Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth
- Upper bounds on the quantifier depth for graph differentiation in first order logic
- Upper bounds on the quantifier depth for graph differentiation in first-order logic
- Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm
- Weisfeiler-Lehman graph kernels
Cited in
(8)- On the descriptive complexity of groups without abelian normal subgroups
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
- On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- Comparative design-choice analysis of color refinement algorithms beyond the worst case
- Logarithmic Weisfeiler-Leman identifies all planar graphs
- A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring
This page was built for publication: The iteration number of colour refinement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842499)
