An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability
cs.DM
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 66 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
- Lov'asz Meets Weisfeiler and Leman
- A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns