{"id":"84ff6b19-8584-4d96-bf9a-bec12db73242","arxiv_id":"2611.17022","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"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.","lead":"This paper disproves several conjectures about how many single-colour changes are needed to turn one colouring of a graph into another. The authors build graphs where the required number of changes is larger than the conjectured clean formula.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's verdict is ACCEPT with high confidence, and the weakest_assumption is the detailed counting in Claims 1 and 2. I have examined those claims and the surrounding proof. The reasoning is sound: Claim 1 uses the fact that if x_i is recoloured exactly twice, then its intermediate colour forces a neighbour to be recoloured more than once. Claim 2 uses the incompatibility of the required orders for unique recolourings of y_ij and y_ji. The counting that follows (y ≥ (|X1| choose 2) + |X2|/2) is a direct consequence. The algebraic manipulation to get r ≥ (3t−4)/2 is correct. I see no logical gap. The paper also provides a second construction (Theorem 4) that is independent and yields a stronger bound for regular graphs. The additional results (Theorems 5, 7, Lemma 6) are not essential to the main claim but provide context. The paper is well-written and the authors are appropriately cautious about open problems. Therefore, I agree with the reader's verdict and see no reason to change it.","tokens_in":17313,"tokens_out":583,"duration_ms":254200,"concrete_test":"Independently verify Claim 2 by constructing a small instance (e.g., t=3, graph G_3) and exhaustively enumerating all shortest recolouring sequences between α and β using a computer search. If any sequence achieves distance less than n + 3μ/2 − 2, the claim would be falsified. This test is feasible because the graph has only 9 vertices and the palette has 6 colours.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim (Theorem 3) is supported by a detailed combinatorial case analysis (Claims 1 and 2) that I have reviewed carefully. The counting argument is explicit, the construction is concrete, and the proof of the lower bound follows directly from the claims. The reader's weakest_assumption correctly identifies that the case analysis is the most delicate part, but I find no missing case or hidden assumption. The argument that a vertex recoloured exactly twice must pass through an intermediate colour is standard in reconfiguration, and the incompatibility of the chronological orders in Claim 2 is correctly argued. The proof of Theorem 4 builds on Theorem 3 with a gadget construction that is clearly described. The additional results (Theorems 5, 7, Lemma 6) are independent and do not affect the main counterexample. The paper also openly discusses limitations and open problems, which strengthens its credibility. I therefore see no load-bearing concern that would undermine the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper constructs explicit counterexamples to several conjectures about the diameter of the reconfiguration graph R_{Δ+2}(G) for proper (Δ+2)-colourings. The main result (Theorem 3) gives a family of graphs with diameter at least n + (3/2)μ - 2, disproving the conjecture that the diameter is always n + μ. Theorem 4 provides Δ-regular counterexamples for even Δ ≥ 8. The paper also proves a matching upper bound for a restricted class (Theorem 5), a general lower bound n + μ/2 (Theorem 7), and an extension to hypergraphs (Lemma 8). The proofs are combinatorial and appear sound.","tokens_in":17596,"tokens_out":5285,"duration_ms":233668,"significance":"If correct, the results resolve several open conjectures in reconfiguration theory, showing that the diameter of R_{Δ+2}(G) is not as simple as previously conjectured. The constructions are explicit and the bounds are concrete. The paper also provides positive results (upper bounds for special classes, general lower bound) that contribute to the understanding of the problem. The open problems section is thoughtful and suggests future directions.","major_comments":[{"comment":"The proof of Claim 1 considers two cases for the intermediate colour c (c = b_j or c = a_j). In the case c = a_j, the argument assumes that if y_ij is not repeated, then its unique recolouring must be from b_i to a_j. However, could y_ij be recoloured from b_i to some other colour (not a_j) and then later to a_j? That would make it repeated, which is already covered. The argument seems to assume that if y_ij is not repeated, it must go directly to a_j. This is correct because the target colour of y_ij in β is a_j, so if it is recoloured only once, it must go directly to a_j. The reasoning is sound, but the presentation could be clearer. I recommend adding a brief justification that a non-repeated vertex must be recoloured directly to its target colour.","section":"Section 2, Claim 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The chronological order argument in Claim 2 is correct but relies on the assumption that the unique recolouring of y_ij occurs between the recolourings of x_j and x_i. The justification is that y_ij must be recoloured after x_j leaves its initial colour (to avoid conflict) and before x_i receives its target colour (to avoid conflict). This is standard and valid. However, the proof could be expanded slightly to explain why the orders are incompatible. The current text is terse; a sentence clarifying that the two chains imply x_i ≺ x_j and x_j ≺ x_i would help. This is a minor clarity issue.","section":"Section 2, Claim 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The derivation of 2r ≥ 3t - 4 from the bounds on y and the definitions of X_1, X_2, X_3 is correct but somewhat involved. I verified the algebra: from r ≥ |X_2| + 2|X_3| + y and y ≥ (|X_1| choose 2) + |X_2|/2, we get 2r ≥ 2|X_2| + 4|X_3| + |X_1|(|X_1|-1) + |X_2| = |X_1|^2 - |X_1| + 3|X_2| + 4|X_3|. Using |X_1| + |X_2| + |X_3| = t, we can rewrite to get 2r ≥ 3t - 4 + (|X_1|-2)^2 + |X_3| ≥ 3t - 4. This is valid. No error.","section":"Section 2, final inequality","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The construction of the regular graphs uses gadgets B_ij obtained from K_{Δ,Δ} minus a matching. The proof that the resulting graph is Δ-regular and that the matching number is t + Δm is clear. However, the lower bound on the diameter relies on the claim that in each B_ij, every vertex must be recoloured and at least one endpoint of each edge of a perfect matching must be recoloured twice. The argument that each copy requires at least 3Δ recolourings is plausible but could be expanded: why exactly 3Δ? The text says 'at least one endpoint of each such edge must therefore be recoloured twice' and then 'Hence each copy requires at least 3Δ recolourings.' Since there are Δ edges in the perfect matching, each edge contributes at least 1 extra recolouring beyond the first per vertex, so at least Δ extra recolourings, plus the 2Δ vertices each recoloured at least once gives 3Δ. This is correct. However, the proof that the two colourings can be extended to the gadgets while maintaining properness and using only the palette of 2t colours is not fully detailed. The authors state 'choose two distinct colours c_ij, d_ij outside {b_i, a_j}' but do not verify that such colours exist in the palette of size 2t = Δ+2. For Δ=8, t=5, palette size 10. The colours b_i and a_j are two specific colours; there are 8 others, so two distinct ones exist. For general even Δ, t = Δ/2+1, palette size Δ+2. The set {b_i, a_j} has size at most 2, so there are at least Δ colours left, which is ≥2 for Δ≥2. So it's fine. The extension to the rest of the gadget is not described; the authors only say 'colour its two parts c_ij, d_ij in α, and interchange these colours in β.' This is insufficient: the gadget B_ij is a graph with 2Δ vertices, not just two parts. The construction says 'take a disjoint copy B_ij of B and join its Δ-2 degree-(Δ-1) vertices to y_ij.' Then 'colour its two parts c_ij, d_ij in α' – what are 'its two parts'? B is obtained from K_{Δ,Δ} minus a matching, so it is bipartite with two parts of size Δ. The authors presumably mean colour all vertices in one part with c_ij and all vertices in the other part with d_ij. But then the vertices in B_ij that are adjacent to y_ij have degree Δ-1 in B and then an extra edge to y_ij, making them degree Δ. The colouring must be proper: y_ij has colour b_i in α, so the neighbours of y_ij in B_ij must not have colour b_i.","section":"Section 3, Theorem 9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Theorem 11 uses a minimal counterexample argument and a digraph D. The reasoning that D is strongly connected is standard. However, the step 'If for some a∈A there is a colour c∈L(a) absent from both α(N(a)) and β(N(a)), then recolour vertex a to c with respect to both α and β. This requires two recolouring steps in total.' This assumes that after recolouring a to c in α, the resulting colouring is still proper. Since c is absent from α(N(a)), it is safe. Similarly for β. The two recolourings are independent and can be done in either order. This is fine. The subsequent counting uses inequality (1) with S={a}. The inequality requires that after fixing a, the remaining graph G-a satisfies the list size conditions. The authors claim 'The conditions on the list sizes are preserved, since each remaining vertex loses at most one colour for each deleted neighbour.' This is true if we remove the colour of the deleted vertex from the lists of its neighbours. But here we are not deleting a vertex; we are fixing it and then considering G-S. The argument is that we can first recolour a to c in both α and β, making them agree on a, then delete a (fix it) and consider the rest. The list sizes for neighbours of a are reduced by at most 1 because a now has colour c, which may be in their lists. The condition |L(v)| ≥ deg(v)+2 (or +3) is preserved because deg(v) decreases by 1 when a is removed, and the list size decreases by at most 1. This is standard and correct. The proof is sound.","section":"Section 4, Theorem 11","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof for λ=3/2 uses a six-step recolouring procedure on a directed path u→b→v. The existence of such a path is justified by strong connectivity and the fact that every b∈B has indegree=outdegree=1. The recolouring steps are described and the justification that they are allowed relies on the uniqueness properties derived from the equality conditions. The argument that y∉α(N(u)) and x∉β(N(v)) is correct. The step where b is recoloured to z: at that moment, its neighbours u and v both have colour y (in the first row) or x (in the second row), so recolouring b to z (which is not x or y) is allowed because z is not used by neighbours. The choice of z∈L(b)\\{x,y} is possible because |L(b)| ≥ deg(b)+2 = 4 (since deg(b)=2) and {x,y} are two colours, so at least two others exist. This is valid. The counting gives dist ≤ 6 + n - 3 + (3/2)(μ-2) = n + 3μ/2. This matches the bound. The proof is correct.","section":"Section 4, final part for λ=3/2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 6 (Lemma 12 in the text) is clear and correct. The construction of two recolouring sequences with lengths ℓ_A and ℓ_B and the averaging argument to get min ≤ 3n/2 is elegant. No issues.","section":"Section 5, Lemma 6","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof constructs a supergraph Ĝ and a proper colouring γ of Ĝ with an involution property. The construction processes edges of M in arbitrary order and chooses colours avoiding previously coloured neighbours. The argument that at most 2Δ-2 colours are forbidden at each step is correct because each endpoint has at most Δ-1 neighbours in the already processed submatching (since each edge of M contributes at most 2 neighbours, but the symmetry ensures that the forbidden sets are related). The construction of the two colourings α and β from γ restricted to a subset U* is clear. The lower bound n + |M*| is justified. The final bound n + min(1, ⌊k/2⌋/Δ) μ is derived. For k=Δ+2, ⌊k/2⌋ = ⌊(Δ+2)/2⌋, so the bound becomes n + (⌊(Δ+2)/2⌋/Δ) μ. For Δ≥2, this is at least n + μ/2. The proof is sound.","section":"Section 6, Theorem 14","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The hypergraph extension is interesting. The proof of the upper bound 2n-1 uses a phase argument. The existence of an uncompleted colour c with |γ^{-1}(c)| ≤ |β^{-1}(c)| is justified by a counting argument. The phase recolours all vertices of colour c to other colours, then recolours β^{-1}(c) to c. The claim that each phase uses at most 2|β^{-1}(c)| steps is correct. The final saving of at least one step is argued: if the last colour d is selected, then we can recolour β^{-1}(d) directly in at most |β^{-1}(d)| steps, saving at least one step compared to the general bound. This gives ≤ 2n-1. The lower bound n is trivial. The proof is correct.","section":"Section 7, Lemma 15","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The abstract says 'diameter at least n+3/2 μ-2' but Theorem 3 states 'n + 3/2 μ - 2'. The abstract uses 'n+3/2 μ-2' without parentheses; it's clear but could be formatted consistently.","section":"Abstract","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Proposition 2 lists known results. The reference to [Zev23] is a bachelor's thesis; it might be acceptable but could be considered a non-peer-reviewed source. This is not a major issue.","section":"Section 1, Proposition 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Figure 1 is described but not included in the text. The caption references 'the graph G_3 with the colourings α (left) and β (right).' The figure is presumably present in the arXiv version. No issue.","section":"Section 2, Figure 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"In the case c = a_j, the text says 'y_ij would still have colour b_i at that time.' This refers to the scenario after x_i is coloured b_i. But y_ij's target colour is a_j, so if it hasn't been recoloured yet, it still has b_i. That's correct. The sentence is slightly ambiguous: 'as y_ij would still have colour b_i at that time' – it might be clearer to say 'because y_ij would still have colour b_i, which conflicts with x_i's colour b_i.' Actually, x_i's colour b_i is the same as y_ij's colour b_i, so that's not a conflict; the conflict is that y_ij cannot be recoloured to a_j while x_i has colour a_j? Wait, the argument: 'It also cannot occur after x_i is coloured b_i, as y_ij would still have colour b_i at that time.' The issue is that if y_ij is recoloured after x_i gets b_i, then y_ij would need to change from b_i to a_j, but x_i already has b_i, so that's fine? Actually, the properness condition: y_ij adjacent to x_i, so they cannot share the same colour. If x_i has b_i and y_ij has b_i, that's a conflict. So y_ij cannot have b_i after x_i gets b_i. Therefore y_ij must be recoloured before x_i gets b_i. The text says 'as y_ij would still have colour b_i at that time' – this is correct because if y_ij hasn't been recoloured, it still has b_i, which would conflict with x_i's b_i. So the argument is valid. The phrasing could be clearer, but it's fine.","section":"Section 2, Claim 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The construction uses B obtained from K_{Δ,Δ} by deleting a matching of size (Δ-2)/2. For Δ even, (Δ-2)/2 is integer. The resulting graph has Δ-2 vertices of degree Δ-1 and the rest degree Δ. The authors then join these Δ-2 vertices to y_ij. This makes them degree Δ. The remaining vertices (the other Δ+2 vertices?) have degree Δ already. The graph becomes Δ-regular. This is correct. However, the description 'join its Δ-2 degree-(Δ-1) vertices to y_ij' could be misinterpreted: there are Δ-2 vertices of degree Δ-1 in B, and each is joined to y_ij. That adds one edge each, making them degree Δ. The other vertices (of degree Δ) are not joined. This yields a Δ-regular graph. The proof that the matching number is t + Δm is given. The lower bound on diameter uses that each B_ij requires at least 3Δ recolourings. The argument that 'at least one endpoint of each such edge must therefore be recoloured twice' refers to a perfect matching in B_ij. But B_ij is obtained from K_{Δ,Δ} minus a matching; does it have a perfect matching? Yes, K_{Δ,Δ} minus a matching still has a perfect matching (since we removed a matching, the remaining graph is still regular of degree Δ-1 on each side? Actually, K_{Δ,Δ} minus a matching of size (Δ-2)/2 leaves a bipartite graph with parts of size Δ, each vertex on one side loses at most one edge (if it was incident to a removed matching edge). The resulting graph may not be regular, but it still contains a perfect matching because Hall's condition holds (each subset of one side has at least as many neighbours on the other side, since the original complete bipartite minus a matching still has high minimum degree). The authors claim 'B has a perfect matching so that μ(B)=Δ.' This is stated earlier. So it's fine.","section":"Section 3, Theorem 9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"In the proof, the authors define a digraph D with an arc u→v when uv∈E(G) and β(u)=α(v). This is a standard construction. The claim that D is strongly connected is justified by a minimal counterexample argument. The argument is correct but relies on the fact that if D is not strongly connected, then there is a nonempty proper subset X with no outgoing arc. Then they claim 'First recolour G[X] from α to β without recolouring any vertex of G-X (this is possible because there is no arc from X to G-X).' The justification for the possibility of recolouring G[X] without recolouring G-X is that there is no arc from X to G-X means that for every edge uv with u∈X, v∉X, we have β(u)≠α(v). This ensures that the colours of vertices in X can be changed without affecting the properness with respect to the fixed colours of G-X. However, the recolouring of G[X] might require recolouring vertices multiple times, but the existence of a sequence is guaranteed by induction on the size of X? The authors seem to assume that the distance within G[X] is bounded by something, but they are constructing a sequence from α to β on the whole graph by first recolouring X to β, then recolouring G-X to β. The first step requires that the restriction of α to X can be transformed to the restriction of β to X without ever using colours that conflict with the fixed colours on G-X. The condition that there is no arc from X to G-X ensures that for every edge uv with u∈X, v∉X, we have β(u)≠α(v). But during the recolouring of X, intermediate colours might conflict with G-X. The standard argument in reconfiguration (e.g., in [CCC24]) uses that if there is no arc from X to G-X, then the colours of vertices in X can be changed independently because the only potential conflicts are with neighbours in G-X, and the condition ensures that the target colours β(u) are not present on neighbours in G-X. However, intermediate colours could still cause conflicts. The usual technique is to first recolour all vertices of X to some colour not used by their neighbours in G-X, then to their target colours. This requires that each vertex has at least one colour not used by its neighbours in G-X. Since k ≥ Δ+2, and each vertex has at most deg(v) neighbours in G-X (which is ≤ Δ), there is at least one colour available.","section":"Section 4, Theorem 11","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof uses the fact that B is independent. This is true because G is bipartite and B is one part. The recolouring steps are described clearly. No issues.","section":"Section 5, Lemma 6","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof constructs a supergraph Ĝ with vertex set U and edges E(G[U]) ∪ {π(x)π(y): xy∈E(G[U])}. The maximum degree of Ĝ is at most 2Δ-1. The construction of γ processes edges of M in arbitrary order. The claim that at each step, each endpoint has at most 2Δ-2 previously coloured neighbours is justified because the previously coloured vertices are endpoints of some submatching, and the symmetry ensures that the forbidden sets are related. The argument is clear. However, the step 'Since |C_u| ≤ 2Δ-2, we can choose a colour c∉C_u. Then σ(c)∉σ(C_u) because σ is an involution, and c≠σ(c) because σ has no fixed point.' This is correct. The construction of γ is valid.","section":"Section 6, Theorem 14","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof uses the concept of 'effective degree' deg*(v). The observation that at most deg*(v) colours are forbidden at v is justified. The phase argument is clear. The final saving of at least one step is argued: 'If some colour d with non-empty β^{-1}(d) is never selected, its contribution is omitted from the sum, saving at least two steps. Otherwise, in the final phase when the last colour d is selected, every vertex outside β^{-1}(d) already has its target colour. Then we can recolour β^{-1}(d) directly to d in at most |β^{-1}(d)| steps, saving at least one step.' This is correct and yields the bound 2n-1.","section":"Section 7, Lemma 15","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The open problems are well-posed and relevant. The paper acknowledges that the results raise more questions than answers, which is appropriate.","section":"Section 8, Open problems","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The declaration states 'Yes and no' and then expands. This is unusual but transparent. It does not affect the mathematical validity.","section":"Declaration of AI use","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The references include several arXiv papers and a bachelor's thesis. This is acceptable for a preprint. Some references are to 'to appear' or '2026' which is fine.","section":"References","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"minor_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Two things up front. The constructions are real, and the n+mu conjecture from CCC24 is dead. I sat down with the proof of Theorem 3 and checked the two claims line by line: the case analysis for a vertex recoloured exactly twice, and the incompatible chronological orders when two X-vertices are both recoloured once. Both hold, and the counting that turns them into the 3/2 lower bound is sound. The reader's flagged weak spot is the right place to look, but it does not bite.\n\nWhat is actually new: Theorem 3 gives explicit bipartite graphs with diameter at least n + 3mu/2 - 2, beating n+mu for mu > 4. Theorem 4 adapts the construction by grafting K_{Delta,Delta} gadgets, producing Delta-regular counterexamples for every even Delta >= 8, which kills the regular case of the conjecture too. Theorem 7's universal lower bound n + mu/2 has a proof I like: colour the pairing-symmetric supergraph with a fixed-point-free involution, split the matching by colour pairs, keep the largest r parts. The one spot I was suspicious of - whether the colour c chosen for a matched edge must avoid both C_u and C_v - resolves fine, because each side only needs separation from its own forbidden set. Theorem 5 is the right complement: within the very class containing their own constructions, the 3/2 factor is asymptotically optimal at k = Delta+2, and equality n+mu returns at k >= Delta+3. The hypergraph section is a genuine but clearly peripheral bonus.\n\nSoft spots, in proportion. The two claims in Section 2 are load-bearing and they rest on shortest-sequence reasoning about intermediate colours; I did not find a missed order, but this is where a referee should sit. Theorem 11's list-colouring proof is dense - the strong connectivity of the digraph D and the six-step exchange at the end are intricate and deserve a careful pass even though the structure is sound. Minor: the remark that another gadget yields 106/105 is asserted without proof, and the AI-use declaration (\"blurry symbiotic mix\") means verification should be genuinely human rather than taken on trust. Neither affects my verdict.\n\nWho this is for: people working in colouring reconfiguration, and anyone tracking exact diameter thresholds near Delta+2. It deserves a serious referee - a counterexample paper that knocks out three published conjectures with constructions explicit enough to verify by hand.\n\nRecommendation: invite the full review, ask specifically for a careful pass on Claims 1-2 and the counting inequality in Theorem 3, and expect minor revisions at worst.","headline":"The paper's explicit constructions genuinely kill the n+mu conjecture from CCC24; I checked the delicate counting in Theorem 3 and it holds.","tokens_in":18085,"tokens_out":15815,"duration_ms":114548},"pith_extraction":{"msc":["05C15","05C35","05C69","05C85"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"The paper disproves the conjecture that the reconfiguration diameter for (Δ+2)-colourings is exactly n + μ, constructing graphs where it is at least n + (3/2)μ - 2.","keywords":["graph colouring","reconfiguration","diameter","matching number","maximum degree","Cereceda conjecture","regular graphs","hypergraphs"],"falsifier":"To test the central claim, one could computationally search for a shortest recolouring sequence between the two constructed colourings α and β for G_t (say t=4, n=16, Δ=6). If a sequence of length < n + (3/2)μ - 2 = 16 + 6 - 2 = 20 is found, the claimed lower bound would be falsified for that t. More generally, a counterexample to the 3/2 coefficient would require a graph where diam ≤ n + cμ with c < 3/2 for all graphs.","tokens_in":18827,"feed_emoji":"🔴","tokens_out":1445,"duration_ms":13356,"temperature":0.7,"pith_summary":"This paper disproves a 2022 conjecture that the diameter of the reconfiguration graph for (Δ+2)-colourings is exactly n + μ (vertices plus matching number). The author constructs graphs where the diameter is at least n + (3/2)μ - 2, and provides regular counterexamples as well. It also proves a universal lower bound of n + μ/2 for all graphs, and extends the study to hypergraphs. The results show the problem is more complex than previously thought, and the paper proposes several open questions.","feed_headline":"Colour-reconfiguration diameter can exceed n + matching number","feed_subtitle":"New constructions force the diameter up to n + 1.5μ, disproving a 2022 conjecture.","key_machinery":"The central object is a bipartite graph G_t formed by subdividing each edge of a doubled complete graph K_t (each edge replaced by a vertex of degree 2). This graph has n = $t^{2}$, Δ = 2t-2, μ = τ = t. Two specific (Δ+2)-colourings α and β are defined using 2t colours. The analysis of a shortest recolouring sequence between them relies on counting repeated vertices (those recoloured at least twice) via two combinatorial claims about forced repetitions among X-vertices and Y-vertices. The counting yields r ≥ (3t-4)/2 extra recolourings beyond n, giving the diameter lower bound.","core_discovery":"The paper constructs families of graphs (specifically, 1-subdivisions of doubled complete graphs) for which the reconfiguration diameter under (Δ+2) colours is strictly larger than n + μ, refuting the conjecture that n + μ is the exact diameter for all graphs. For these graphs, the diameter is at least n + (3/2)μ - 2, establishing that the coefficient of μ can be at least 3/2, not 1. Additionally, it constructs Δ-regular graphs with diameter exceeding n + μ, disproving the regular case conjecture. The paper also proves a universal lower bound of n + μ/2 for all graphs, and shows sharp upper bounds for certain bipartite classes.","pith_inferences":["The counterexample construction (subdivision of doubled complete graph) is very specific; it would be interesting to see if other graph families also force the coefficient above 1, or if the 3/2 bound is tight for some natural class.","The paper leaves open the exact worst-case coefficient ϵ such that diam ≤ n + ϵμ for all graphs. The results narrow the range to [3/2, 2], but the true value remains unknown. Determining ϵ might require new structural insights.","The hypergraph extension suggests that the linear diameter phenomenon is robust beyond graphs, but the exact dependence on matching number or other parameters for hypergraphs is unexplored.","The open problem about the stability threshold k_Δ (the smallest k where diameter equals n+μ for all Δ-degree graphs) is intriguing; the results show k_Δ ≥ Δ+3 for many Δ, but the exact threshold may vary with Δ."],"forward_implications":["The 2022 conjecture that diam R_{Δ+2}(G) = n + μ for all graphs G is false; the true maximum coefficient of μ is at least 3/2 and at most 2.","For Δ-regular graphs, the diameter can exceed n + μ, disproving the 'Regular Cereceda Conjecture'.","Every graph satisfies diam R_{Δ+2}(G) ≥ n + μ/2, a universal lower bound that improves on the trivial n lower bound.","For bipartite graphs where one part has degree at most 2, the upper bound n + (3/2)μ is sharp, matching the lower bound from the counterexample construction.","The reconfiguration diameter for hypergraphs with k ≥ Δ*+2 is between n and 2n-1, linear in n."],"supporting_citations":[{"why":"The 2022 paper by Cambie, Cames van Batenburg, and Cranston that proved the upper bound diam ≤ n+2μ and formulated the conjectures that this paper disproves.","marker":"[CCC24]"},{"why":"De Meyer's result that diam = n+μ for subcubic graphs and complete multipartite graphs, which provided evidence for the conjectures.","marker":"[DM26]"},{"why":"Jerrum's exponential upper bound on the reconfiguration diameter, the starting point for the line of work improved by Cereceda and then by [CCC24].","marker":"[Jer95]"},{"why":"Cereceda's thesis that improved the diameter bound to O(nΔ), later improved to linear by [CCC24].","marker":"[Cer07]"},{"why":"Bonamy and Bousquet's lemma on complete graphs that inspired the 3n/2 bound conjecture (Conjecture 19).","marker":"[BB18]"}],"fun_headline_variants":["Rainbow reconfiguration distances defy conjectured bound","Graph colouring swaps need more steps than predicted","Colour-shift graph diameter stretches past n plus matching number","Disproved: matching number does not cap reconfiguration distance","Recolouring paths can be longer than n + μ"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The lower bound argument for Theorem 3 depends on a detailed case analysis (Claims 1 and 2) that assumes any shortest recolouring sequence must satisfy certain chronological constraints; if there exists an alternative sequence that avoids some of the forced repeated vertices, the constant 3/2 might not be attainable for the constructed graphs.","fun_headline_variants_meta":{"raw":{"variants":["Rainbow reconfiguration distances defy conjectured bound","Graph colouring swaps need more steps than predicted","Colour-shift graph diameter stretches past n plus matching number","Disproved: matching number does not cap reconfiguration distance","Recolouring paths can be longer than n + μ"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":8.6e-05,"raw_usage":{"cost":8.62862e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":8.62862e-05,"upstream_inference_prompt_cost":7.19082e-05,"upstream_inference_completions_cost":1.4378e-05},"total_tokens":1074,"prompt_tokens":995,"completion_tokens":79,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":995,"tokens_out":79,"cost_source":"openrouter_usage","duration_ms":4116,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T07:21:01.165201+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"To test the central claim, one could computationally search for a shortest recolouring sequence between the two constructed colourings α and β for G_t (say t=4, n=16, Δ=6). If a sequence of length < n + (3/2)μ - 2 = 16 + 6 - 2 = 20 is found, the claimed lower bound would be falsified for that t. More generally, a counterexample to the 3/2 coefficient would require a graph where diam ≤ n + cμ with c < 3/2 for all graphs.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}