Metraipolis › archive › dc_030c5d454285

Sharp Bounds for Common Spanning Forests under Color Refinement — arXiv:2610.22909

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.22909
License (as archived)
CC0-1.0
Archived
2026-10-19T09:39:23.415Z
SHA-256 of the archived text
db7ee38b6d55bb5c7077223dad1bc4c1e4185658467e1c770202d6d06f4265bc
Stable URL of this page
https://metraipolis.com/documento/dc_030c5d454285

How to cite

Sharp Bounds for Common Spanning Forests under Color Refinement — arXiv:2610.22909 — arXiv (en), https://arxiv.org/abs/2610.22909 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_030c5d454285 (Metraipolis archive dc_030c5d454285, sha256 db7ee38b6d55bb5c7077223dad1bc4c1e4185658467e1c770202d6d06f4265bc)
BibTeX
@misc{dc030c5d454285,
  title = {Sharp Bounds for Common Spanning Forests under Color Refinement — arXiv:2610.22909},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.22909},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_030c5d454285; sha256 db7ee38b6d55bb5c7077223dad1bc4c1e4185658467e1c770202d6d06f4265bc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22909. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\ge2$ contain isomorphic spanning forests with at most $r-1$ components. This bound depends only on $r$ and is sharp for every $r\ge2$. 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)$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.22909 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:34:59.739Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).