PreprintarXiv licencearXiv
Sharp Bounds for Common Spanning Forests under Color Refinement
Abstract
We study the common spanning structure of connected finite simple graphs that are indistinguishable by uniformly initialized color refinement. We prove that any two such graphs with common cyclomatic number r≥2 contain isomorphic spanning forests with at most r−1 components. This bound depends only on r and is sharp for every r≥2, even when both graphs have maximum degree at most three. We also determine the maximum, over all such graph pairs without restricting their order, of the minimum edge symmetric difference under vertex bijections: it is exactly 4(r−1).
Related
- A sharp upper bound on the number of spanning forests of regular graphs
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- A zero-one law for swap-invariant events in uniform spanning forests
- β-Skewed Maximal Spanning Forests
- Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
BibTeX
@misc{zhu2026sharp,
title = {{Sharp Bounds for Common Spanning Forests under Color Refinement}},
author = {Jianshen Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22909},
eprint = {2610.22909},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22909},
}
RIS
TY - UNPB
TI - Sharp Bounds for Common Spanning Forests under Color Refinement
AU - Jianshen Zhu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.22909
UR - https://arxiv.org/abs/2610.22909
AB - We study the common spanning structure of connected finite simple graphs that are indistinguishable by uniformly initialized color refinement. We prove that any two such graphs with common cyclomatic number r≥2 contain isomorphic spanning forests with at most r−1 components. This bound depends only on r and is sharp for every r≥2, even when both graphs have maximum degree at most three. We also determine the maximum, over all such graph pairs without restricting their order, of the minimum edge symmetric difference under vertex bijections: it is exactly 4(r−1).
ER -