Pith.

Combinatorics · arXiv:2611.17022 v1 · submitted 12 Nov 2026 · 58 references

Large diameter for (Δ + 2)-colouring reconfiguration

Wouter Cames van Batenburg

The paper says

“Given a graph G and an integer k, the reconfiguration graph ℛ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.”

more of the abstract

In 2022, Cambie, Cranston and the author proved that the diameter of ℛΔ + 2(G) is at most n + 2μ, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of ℛΔ + 2(G) is precisely equal to n + μ, for every graph G with n vertices, matching number μ and maximum degree Δ. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least n + 3/2μ−2. We also provide counterexamples that are Δ-regular, we show that every graph has reconfiguration diameter at least n + 1/2μ, 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.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up. The paper's explicit constructions genuinely kill the n+mu conjecture from CCC24; I checked the delicate counting in Theorem 3 and it holds. This line is wrong

9 major objections · 12 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 58 references say.

The paper says, at Section 2, Claim 1

The review did not quote this passage.

Pith says: Objection 1 of 9 · major

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.

more of objection 1

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.

The paper says, at Section 2, Claim 2

The review did not quote this passage.

Pith says: Objection 2 of 9 · major

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).

more of objection 2

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.

The paper says, at Section 2, final inequality

The review did not quote this passage.

Pith says: Objection 3 of 9 · major

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|.

more of objection 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.

The paper says, at Section 3, Theorem 9

The review did not quote this passage.

Pith says: Objection 4 of 9 · major

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.

more of objection 4

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.

The paper says, at Section 4, Theorem 11

The review did not quote this passage.

Pith says: Objection 5 of 9 · major

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 β.

more of objection 5

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.

This review says the paper's mathematics is wrong. Pith did not check that against the paper's source.

The paper says, at Section 4, final part for λ=3/2

The review did not quote this passage.

Pith says: Objection 6 of 9 · major

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.

more of objection 6

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.

The paper says, at Section 5, Lemma 6

The review did not quote this passage.

Pith says: Objection 7 of 9 · major

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.

The paper says, at Section 6, Theorem 14

The review did not quote this passage.

Pith says: Objection 8 of 9 · major

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).

more of objection 8

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.

The paper says, at Section 7, Lemma 15

The review did not quote this passage.

Pith says: Objection 9 of 9 · major

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.

more of objection 9

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.

12 minor objections

The paper says, at Abstract

Pith says: minor objection 1 of 12

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.

The paper says, at Section 1, Proposition 2

Pith says: minor objection 2 of 12

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.

show 10 more

The paper says, at Section 2, Figure 1

Pith says: minor objection 3 of 12

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.

The paper says, at Section 2, Claim 1

Pith says: minor objection 4 of 12

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.

more of objection 4

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.

The paper says, at Section 3, Theorem 9

Pith says: minor objection 5 of 12

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.

more of objection 5

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.

The paper says, at Section 4, Theorem 11

Pith says: minor objection 6 of 12

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.

more of objection 6

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.

The paper says, at Section 5, Lemma 6

Pith says: minor objection 7 of 12

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.

The paper says, at Section 6, Theorem 14

Pith says: minor objection 8 of 12

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.

more of objection 8

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.

The paper says, at Section 7, Lemma 15

Pith says: minor objection 9 of 12

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.

more of objection 9

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.

The paper says, at Section 8, Open problems

Pith says: minor objection 10 of 12

The open problems are well-posed and relevant. The paper acknowledges that the results raise more questions than answers, which is appropriate.

The paper says, at Declaration of AI use

Pith says: minor objection 11 of 12

The declaration states 'Yes and no' and then expands. This is unusual but transparent. It does not affect the mathematical validity.

The paper says, at References

Pith says: minor objection 12 of 12

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.

What would settle it

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.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up confidence high
  2. Skeptic agrees 4 min 14 s · 17,313 tokens read, 583 written
  3. Editor wrote the verdict above 1 min 55 s · 18,085 tokens read, 15,815 written
  4. Referee minor revision: 9 major objections, 12 minor 3 min 54 s · 17,596 tokens read, 5,285 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

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.

What 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 KDelta,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 Cu and Cv - 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.

Soft 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.

Who 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.

Recommendation: 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.

The strongest objection

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.

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.

The referee's report

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.

Pith's reading of the paper (a machine's summary, not the authors')

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.

What carries the argument. 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 claim. 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.

The premise it rests on. 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.

If the paper is right (Pith's inferences, not the authors')

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.

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 Δ.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

Given a graph G and an integer k, the reconfiguration graph ℛ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 ℛΔ + 2(G) is at most n + 2μ, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of ℛΔ + 2(G) is precisely equal to n + μ, for every graph G with n vertices, matching number μ and maximum degree Δ. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least n + 3/2μ−2. We also provide counterexamples that are Δ-regular, we show that every graph has reconfiguration diameter at least n + 1/2μ, 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.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-13

The authors' main claim, as the classifier picked it out 0.99

“Here we disprove most of those conjectures.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.75 · human participants 0.01 · controlled comparison 0.04 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.94 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
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$. background 1.00 0.04 0.02 asserted 0.98
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$. background 1.00 0.73 0.05 asserted 0.96
Here we disprove most of those conjectures. result 0.65 0.94 0.61 asserted 1.00
Our constructions have reconfiguration diameter at least $n+\frac{3}{2}\mu-2$. result 0.99 0.97 0.51 asserted 1.00
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. result 0.87 0.96 0.13 asserted 1.00
It is now much more mysterious how the diameter behaves, so we propose a number of open problems. future work 0.97 0.51 0.06 asserted 0.79

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 0.99

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 5,189 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (2)
Figure 1 of the paper
Figure 1. The graph G3 with the colourings α (left) and β (right). Proof of Theorem 3. For t ≥ 2, let Gt be the bipartite graph with parts X = {x1, . . . , xt} and Y = {yij : 1 ≤ i, j ≤ t, i ̸= j}, where the neighbourhood of yij is {xi , xj}, for every i ̸= j. Thus Gt is obtained by subdividing once every edge of the multigraph formed by doubling each edge of the complete graph Kt . The number of vertices, maximum degree, matching number and vertex cover number of Gt are n(Gt) = t 2 , ∆(Gt) = 2t − 2, µ(Gt) = τ(Gt) = t. Indeed, X is a vertex cover so that µ(Gt) ≤ τ(Gt) ≤ t, and the edges…
Figure 2 of the paper
Figure 2. , and the colourings of G3 are illustrated in

Figures are the authors', reproduced from the paper.

References (58)
  1. [1] Bartier, Valentin and Bousquet, Nicolas and Feghali, Carl and Heinrich, Marc and Moore, Benjamin and Pierron, Th. Recoloring planar graphs of girth at least five , journal =. 2023 , doi = on Pith
  2. [2] Bartier, Valentin and Bousquet, Nicolas and Heinrich, Marc , title =. Discrete Mathematics , volume =. 2021 , doi = on Pith
  3. [3] Belavadi, Manoj and Cameron, Kathie , title =. Discrete Applied Mathematics , volume =. 2025 , doi = on Pith
  4. [4] Belavadi, Manoj and Cameron, Kathie and Hildred, Elias , title =. Electronic Journal of Combinatorics , volume =. 2025 , doi = on Pith
  5. [5] Belavadi, Manoj and Cameron, Kathie and Merkel, Owen , title =. European Journal of Combinatorics , volume =. 2024 , doi = on Pith
  6. [6] Belavadi, Manoj and Cameron, Kathie and Sintiari, Ni Luh Dewi , title =. Journal of Graph Theory , volume =. 2026 , doi = on Pith
  7. [7] Bonamy, Marthe and Bousquet, Nicolas , title =. European Journal of Combinatorics , volume =. 2018 , doi = on Pith
  8. [8] Bonamy, Marthe and Johnson, Matthew and Lignos, Ioannis and Patel, Viresh and Paulusma, Dani. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs , journal =. 2014 , doi = on Pith
  9. [9] Bonsma, Paul and Cereceda, Luis , title =. Theoretical Computer Science , volume =. 2009 , doi = on Pith
  10. [10] Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika. Short and local transformations between. Innovations in Graph Theory , volume =. 2025 , doi = on Pith
  11. [11] Bousquet, Nicolas and Heinrich, Marc , title =. Journal of Combinatorial Theory, Series B , volume =. 2022 , doi = on Pith
  12. [12] Bousquet, Nicolas and Mouawad, Amer E. and Nishimura, Naomi and Siebertz, Sebastian , title =. Computer Science Review , volume =. 2024 , doi = on Pith
  13. [13] Bousquet, Nicolas and Perarnau, Guillem , title =. European Journal of Combinatorics , volume =. 2016 , doi = on Pith
  14. [14] Cambie, Stijn and. Optimally reconfiguring list and correspondence colourings , journal =. 2024 , doi = on Pith
  15. [15] Cambie, Stijn and. Sharp bounds on lengths of linear recolouring sequences , journal =. 2026 , doi = on Pith
  16. [16] Cambie, Stijn and. Reconfiguration of list colourings , year = on Pith
  17. [17] Cereceda, Luis , title =. 2007 , url = on Pith
  18. [18] Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew , title =. Discrete Mathematics , volume =. 2008 , doi = on Pith
  19. [19] Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew , title =. European Journal of Combinatorics , volume =. 2009 , doi = on Pith
  20. [20] Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew , title =. Journal of Graph Theory , volume =. 2011 , doi = on Pith
show 38 more
  1. [21] Cranston, Daniel W. , title =. European Journal of Combinatorics , volume =. 2022 , doi = on Pith
  2. [22] Cranston, Daniel W. , title =. European Journal of Combinatorics , volume =. 2025 , doi = on Pith
  3. [23] De Meyer, Lucas , title =. Discrete Mathematics , volume =. 2026 , doi = on Pith
  4. [24] Dvo. An update on reconfiguring. Electronic Journal of Combinatorics , volume =. 2020 , doi = on Pith
  5. [25] Dvo. A. European Journal of Combinatorics , volume =. 2021 , doi = on Pith
  6. [26] Echeverr. Yes,. 2026 , arxiv = on Pith
  7. [27] Feghali, Carl , title =. Journal of Combinatorial Theory, Series B , volume =. 2021 , doi = on Pith
  8. [28] Feghali, Carl and Johnson, Matthew and Paulusma, Dani. A reconfigurations analogue of. Journal of Graph Theory , volume =. 2016 , doi = on Pith
  9. [29] Gu, Ruijuan and Lei, Hui and Li, Zhaoxiang and Ma, Yulai and Wang, Susu , title =. 2026 , arxiv = on Pith
  10. [30] van den Heuvel, Jan , title =. Surveys in Combinatorics 2013 , series =. 2013 , doi = on Pith
  11. [31] Huang, Tianyu and Ma, Yulai and Zhang, Jiaqi , title =. 2026 , arxiv = on Pith
  12. [32] Jerrum, Mark , title =. Random Structures & Algorithms , volume =. 1995 , doi = on Pith
  13. [33] Lei, Hui and Ma, Yulai and Miao, Zhengke and Shi, Yongtang and Wang, Susu , title =. Annals of Applied Mathematics , volume =. 2024 , doi = on Pith
  14. [34] Ma, Yulai and Wang, Susu , title =. Applied Mathematics and Computation , volume =. 2027 , doi = on Pith
  15. [35] Mynhardt, C. M. and Nasserasr, S. , title =. 50 Years of Combinatorics, Graph Theory, and Computing , publisher =. 2020 , doi = on Pith
  16. [36] Nishimura, Naomi , title =. Algorithms , volume =. 2018 , doi = on Pith
  17. [37] Wang, Hongyang , title =. 2026 , arxiv = on Pith
  18. [38] Wang, Yichen and Lu, Mei , title =. Discrete Mathematics , volume =. 2026 , doi = on Pith
  19. [39] Zeven, K. B. , title =. 2023 , url = on Pith
  20. [40] Bondy, J. Adrian and Murty, U. S. R. , title =. 2008 , doi = on Pith
  21. [41] Chudnovsky, Maria and Ries, Bernard and Zwols, Yori , title =. Discrete Applied Mathematics , volume =. 2011 , doi = on Pith
  22. [42] Dyer, Martin and Flaxman, Abraham D. and Frieze, Alan M. and Vigoda, Eric , title =. Random Structures & Algorithms , volume =. 2006 , doi = on Pith
  23. [43] Merkel, Owen , title =. Discrete Mathematics , volume =. 2022 , doi = on Pith
  24. [44] Bonamy, Marthe and Bousquet, Nicolas , title =. Electronic Notes in Discrete Mathematics , volume =. 2013 , doi = on Pith
  25. [45] Laskar, Renu and Lyle, Jeremy , title =. Discrete Applied Mathematics , volume =. 2009 , doi = on Pith
  26. [46] Bonamy, Marthe and Bousquet, Nicolas and Perarnau, Guillem , title =. Combinatorics, Probability and Computing , volume =. 2021 , doi = on Pith
  27. [47] Eiben, Eduard and Feghali, Carl , title =. Journal of Graph Theory , volume =. 2020 , doi = on Pith
  28. [48] Feghali, Carl and Merkel, Owen , title =. Discrete Mathematics , volume =. 2022 , doi = on Pith
  29. [49] Johnson, Matthew and Kratsch, Dieter and Kratsch, Stefan and Patel, Viresh and Paulusma, Dani. Finding shortest paths between graph colourings , journal =. 2016 , doi = on Pith
  30. [50] Bousquet, Nicolas and Bartier, Valentin , title =. 27th Annual European Symposium on Algorithms (ESA 2019) , series =. 2019 , doi = on Pith
  31. [51] Cranston, Daniel W. and Mahmoud, Reem , title =. Journal of Graph Theory , volume =. 2024 , doi = on Pith
  32. [52] Dai, Tingting and Liu, Runrun , title =. Discrete Mathematics , volume =. 2026 , doi = on Pith
  33. [53] Feghali, Carl , title =. Graphs and Combinatorics , volume =. 2020 , doi = on Pith
  34. [54] Zheng, Ruilin and Lu, Junying , title =. 2026 , arxiv = on Pith
  35. [55] Asgarli, Shamil and Krehbiel, Sara and MacLean, Simon and Zaimi, Gjergji , title =. 2025 , arxiv = on Pith
  36. [56] L. On decomposition of graphs , journal = on Pith
  37. [57] Gary Chartrand and Hudson V. Kronk and Curtiss E. Wall , title =. Israel Journal of Mathematics , volume =. 1968 , doi = on Pith
  38. [58] Lucas Picasarri-Arrieta , title =. Journal of Graph Theory , volume =. 2024 , doi = on Pith

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment