{"arxiv_id":"2611.17022","title":"Large diameter for $(\\Delta+2)$-colouring reconfiguration","abstract":"Given a graph $G$ and an integer $k$, the reconfiguration graph $\\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\\mathcal{R}_{\\Delta+2}(G)$ is at most $n+2\\mu$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\\mathcal{R}_{\\Delta+2}(G)$ is precisely equal to $n + \\mu$, for every graph $G$ with $n$ vertices, matching number $\\mu$ and maximum degree $\\Delta$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\\frac{3}{2}\\mu-2$. We also provide counterexamples that are $\\Delta$-regular, we show that every graph has reconfiguration diameter at least $n+\\frac{1}{2} \\mu$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.","primary_cat":"math.CO","cross_cats":["cs.DM"],"submitted_at":"2026-11-12T16:11:10+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"ACCEPT","confidence":"HIGH","one_line_summary":"The paper constructs graphs whose (Delta+2)-colouring reconfiguration diameter is at least n + 3mu/2 - 2, disproving conjectures that it equals n + mu.","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.17022","verdict":"/api/v1/verdicts/2611.17022"}}