{
  "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\\ge2$ contain isomorphic spanning forests with at most $r-1$ components. This bound depends only on $r$ and is sharp for every $r\\ge2$, 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)$.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.22909",
  "author_total": 1,
  "authors": [
    {
      "name": "Jianshen Zhu"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/2f3xx3cgypkx2.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.22909",
  "fulltext_url": null,
  "id": "2f3xx3cgypkx2",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.22909",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7222966168",
  "pdf_url": "https://arxiv.org/pdf/2610.22909",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-26",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/2f3xx3cgypkx2.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:35:40Z",
      "native_id": "2610.22909",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.22909"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Sharp Bounds for Common Spanning Forests under Color Refinement",
  "title_text": "Sharp Bounds for Common Spanning Forests under Color Refinement",
  "type": "preprint",
  "updated_at": "2026-10-30T12:35:40Z",
  "url": "https://research.draconitic.com/paper/2f3xx3cgypkx2",
  "venue": "arXiv",
  "versions": []
}