WorksMathematics
Large diameter for -colouring reconfiguration
Abstract
Given a graph and an integer , the reconfiguration graph has the proper -colourings of for vertices, two of which are adjacent if and only if they differ on precisely one vertex of . In , Cambie, Cranston and the author proved that the diameter of is at most , and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of is precisely equal to , for every graph with vertices, matching number and maximum degree . Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least . We also provide counterexamples that are -regular, we show that every graph has reconfiguration diameter at least , 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.
Introduction
Given a set of objects and a prescribed collection of reversible moves, one can define an associated reconfiguration graph , with vertex set , and two distinct objects adjacent if and only if one can be obtained from the other by a single allowed move. Typically, the moves are chosen to reflect a small local modification of the object, so that the distance in between is a good measure for how closely related and are. More precisely, reconfiguration graphs form a model for how easily two objects can be converted into each other via a sequence of (small) changes, while staying inside the space of relevant objects.
In the classic example, is the set of configurations of a Rubik’s cube, and the allowed moves are the turns of the cube. Then the diameter of is the maximum number of turns required to convert any two given configurations into each other. In particular, this upper bounds the maximum number of moves needed to solve any Rubik’s cube. In more serious situations, may represent the possible states of a physical, chemical or biological system. We refer to the surveys [34, 30] for various other examples.
In one of the most well-studied settings, is the set of proper -vertex-colourings of some fixed graph , for some positive integer . Under the canonical reconfiguration rule, two -colourings are adjacent if and only if they differ on precisely one vertex of . From now on we only consider this type of reconfiguration graph, and we denote it by .
Connectivity and the diameter of have been studied in relation to various graph parameters and structural restrictions, including degeneracy [24, 14, 12], maximum average degree [27, 21 ZL26], bipartite graphs [17, 1], treewidth [2, 3, 5, 36], excluded minors [GLL+26], planar graphs [DF21, BBF+23, CM24, Cra25, DL26], and excluded induced subgraphs (especially for equal to one plus the chromatic number) [13, 3, 7, 8 LMM+24, 9 BCS26]. In this current work, we focus on the maximum degree [31, 28, 6, 15, 11, 16, 26].
Let and denote the maximum degree and number of vertices of , respectively. Complete graphs show that can be empty or disconnected when . However, it is connected (and hence has finite diameter) whenever . In this range, Jerrum [31] in fact gave an argument that implies an exponential upper bound on the diameter. Cereceda [18] subsequently improved this to , and hence . Finally, Cambie, the author, and Cranston [15] showed that the diameter is linear in , namely at most .
This is close to optimal: by relabelling colours one obtains two colourings that differ at every vertex, so for every graph the diameter of must be at least . Inspired by the fact that for complete graphs , and via the intermediate Conjecture 19 mentioned at the end of this manuscript, three refined conjectures on the exact value of the diameter were formulated. Recall that the matching number of a graph is the maximum number of vertex-disjoint edges and the vertex cover number is the smallest size of a vertex set that contains at least one endpoint of every edge. The inequality holds for every graph, with equality for bipartite graphs due to König’s Theorem.
Conjecture 1. [15] For every graph with vertices, maximum degree , matching number and vertex cover number ,
(i) ;
(ii) ;
(iii) if is regular.
On the lower bound side, it was also asked in [15] whether for every graph . This suggested the tantalizingly beautiful possibility of equality for every graph and . The following proposition gives a nonexhaustive selection of evidence from the literature that was gathered in support of this, and Conjecture 1 in particular.
Proposition 2. [15, 26, 37] For every graph with vertices, maximum degree and matching number ,
(i) for all ;
(ii) for all ;
(iii) for all , provided is bipartite;
(iv) for all , provided or is complete multipartite or a tree.
Counterexamples
Conjectures 1.(i) and 1.(ii) are special cases of the Correspondence Colouring Reconfiguration Conjecture and the List Colouring Reconfiguration Conjecture, respectively, and Conjecture 1.(iii) was called the Regular Cereceda Conjecture in [15]. We disprove all of them via Theorems 3 and 4 below.
Theorem 3. For every integer , there is a graph with vertices, maximum degree and matching number and vertex cover number , such that
Theorem 4. There exist 8-regular graphs such that . Moreover, for all even there exists a -regular graph such that
Additional results
Each graph constructed in the proof of Theorem 3 is the 1-subdivision of a multigraph. Therefore they are bipartite, such that all vertices in one of the two parts have degree 2. The following converse theorem shows that the factor is the asymptotically optimal coefficient of within that class of bipartite graphs.
Theorem 5. Let be a bipartite graph such that all vertices in one of the parts have degree at most 2. If , then
If , then
We complement this with a simple bound for bipartite graphs in terms of only the number of vertices, which appears to have eluded explicit statement in the literature. It is sharp due to balanced complete bipartite graphs.
Lemma 6. Let be a bipartite graph. If , then .
Finally, we provide a lower bound that is valid for all graphs.
Theorem 7. Let be a graph. If , then
In a different direction, we present an extension to hypergraphs , showing that in that setting the diameter of the reconfiguration graph is linear in the number of vertices as well. The exact value of the diameter may be more elusive than for graphs, even when the number of colours is large. We refer to § 6 for the relevant definitions and two illustrative corollaries concerning acyclic colourings and partitions into induced forests.
Lemma 8. Let be a loopless hypergraph on vertices and let . Then
Organization
The main result Theorem 3 is proved in § 2. After that, in Section 3 we modify the construction to obtain regular graphs that certify Theorem 4. In the remaining sections we prove Lemmas 6 and 8 and stronger forms of Theorem 5 and Theorem 7. We end with a number of open problems.
Highly nonregular counterexamples
In this section, we prove Theorem 3: for every there exists a graph on vertices with matching number and maximum degree such that the reconfiguration graph of proper -colourings of has diameter at least . The construction is a subdivision of a complete multigraph. See Figure 1 for an illustration of .
Figure 1. The graph with the colourings (left) and (right).
We now give the details.
Proof of Theorem 3. For , let be the bipartite graph with parts
where the neighbourhood of is , for every . Thus is obtained by subdividing once every edge of the multigraph formed by doubling each edge of the complete graph . The number of vertices, maximum degree, matching number and vertex cover number of are
Indeed, is a vertex cover so that , and the edges (with indices modulo ) form a matching so that . We now define two -colourings and , and we will show that they are at distance at least . Use distinct colours , and define and by
The restrictions of these colourings to the subgraph induced by are shown in Figure 2, and the colourings of are illustrated in Figure 1.
!The two colourings (left) and (right) restricted to the induced subgraph bbox=0.24,0.63,0.76,0.78
Figure 2. The two colourings (left) and (right) restricted to the induced subgraph .
Both colourings and are proper, and they differ at every vertex. Therefore every vertex will have to be recoloured at least once, requiring at least recolourings. Consider any shortest recolouring sequence from to , and write its length as , where counts recolourings beyond the first at each vertex. Call a vertex repeated if it is recoloured at least twice.
Claim 1. If is recoloured exactly twice, then it has a repeated neighbour in .
Proof. Suppose is recoloured exactly twice, following for some . If for some , then must leave before leaves . Its first recolouring therefore cannot be directly to its target colour , so is repeated. If for some , suppose that is not repeated. Its unique recolouring must then be from to . This cannot occur before gets colour , as it would block that recolouring. It also cannot occur while has colour , as this would violate properness. It also cannot occur after is coloured , as would still have colour at that time. Thus is repeated. ◇
Claim 2. If and are both recoloured exactly once, then at least one of is repeated.
Proof. Suppose that neither nor is repeated. Then each is recoloured exactly once. Writing when the unique recolouring of precedes the unique recolouring of , properness requires and . These chronological orders are incompatible. Hence at least one of is repeated. ◇
Let denote the disjoint sets of -vertices that are recoloured once, twice, and at least three times, respectively, so . Let be the number of repeated -vertices. Then
By Claim 2, there are at least repeated -vertices whose endpoints are both in . Disjoint from that, by Claim 1, there are at least repeated -vertices adjacent to some vertex of , where the division by 2 is because an -vertex could be adjacent to two vertices from . Hence
Therefore . It follows that the diameter of is at least
Theorem 9. For every even , there exists a -regular graph such that
Proof. Fix an even , put and , and take the graph with parts and colourings that were constructed in the proof of Theorem 3. Thus , every has degree , and every has degree two.
Let be obtained from the complete bipartite graph by deleting a matching of size . Exactly vertices of have degree , and the remaining vertices have degree . Moreover, note that and has a perfect matching so that . For each ,
@page 5/15 starts_mid=1 ends_mid=1
Theorem 9. For every even , there exists a -regular graph such that
Proof. Fix an even , put and , and take the graph with parts and colourings that were constructed in the proof of Theorem 3. Thus , every has degree , and every has degree two.
Let be obtained from the complete bipartite graph by deleting a matching of size . Exactly vertices of have degree , and the remaining vertices have degree . Moreover, note that and has a perfect matching so that . For each , take a disjoint copy of and join its degree- vertices to . The resulting graph is -regular, and
For the matching-number lower bound, combine a maximum matching of with a perfect matching in each . Conversely, a matching uses at most one edge between and for each . If it uses one, then at most edges remain inside , and otherwise at most . Thus any given matching has at most edges with an endpoint in , for every , and at most further edges lie in .
Next we lower bound the diameter of the reconfiguration graph of . Extend to using the same palette of colours that was used for . In each , choose two distinct colours outside , colour its two parts in , and interchange these colours in . Both extensions are proper, since and .
Consider any recolouring sequence between these extensions. Its restriction to requires at least recolourings, by the proof of Theorem 3 and integrality. In each , every vertex must be recoloured, and the colours on each edge of a perfect matching are interchanged. At least one endpoint of each such edge must therefore be recoloured twice. Hence each copy requires at least recolourings. These vertex sets are disjoint, so
Corollary 10. There exist infinitely many -regular graphs with .
Proof. The construction in the proof of Theorem 9 yields an -regular graph with matching number , such that . Now take disjoint copies of . The resulting graph satisfies .
We remark that the construction and computation of Corollary 10 generalizes to all even . For every even integer , there exist infinitely many -regular graphs such that . Furthermore, we elected to give the simplest construction and proof for Theorem 9, by using the gadget obtained from minus a matching. With other choices it is possible to do slightly better. For instance, Theorem 9 also holds with , a complete graph minus the disjoint union of a cycle of length and two edges. Since the resulting -regular graph is smaller, for the analogue of Corollary 10 then gives a better bound .
Bipartite graphs with degree at most two on one side
In this section we prove Theorem 5. The lower bound directly follows from [15 Proposition 3]: for every bipartite graph and every . Therefore we only need to prove upper bounds, which we will do in a stronger form to facilitate induction. Given a graph and a list-assignment , an -colouring (or list colouring) is a proper vertex colouring such that for every vertex . The -colouring reconfiguration graph of a graph has as vertices the -colourings of , two of which are adjacent if they differ on precisely one vertex of . Since -colourings (for ) are special cases of list colourings, the following implies the upper bounds in Theorem 5.
Theorem 11. Let be bipartite with bipartition , where for every .
If for every vertex , then .
If for every and for every , then .
Proof. Fix one of the two statements, and let be its coefficient of . Suppose that it is false, and choose a counterexample of minimum order, with -colourings at distance greater than , where and . The cases are immediate.
We repeatedly use the following observation. If some recolourings of and make them agree on a set , using recolouring steps in total, we may fix and delete , removing its colours from the lists of its remaining neighbours. The conditions on the list sizes are preserved, since each remaining vertex loses at most one colour for each deleted neighbour. Minimality therefore gives
Let be the digraph with an arc whenever and . (Note that an arc means that the current colour of blocks from being directly recoloured to its target colour .) We claim that is strongly connected. Otherwise, choose a nonempty proper subset with no outgoing arc. First recolour from to without recolouring any vertex of (this is possible because there is no arc from to ). Subsequently recolour from to .
Since , applying inequality (1) to and to gives a sequence of length at most , a contradiction. Thus is strongly connected. In particular, is connected and for every vertex.
If is a tree, then follows from [15 Corollary 18]. We may therefore assume that contains a cycle. In this case . Since is one part of the bipartition, the inequality is immediate. For the reverse inequality, take a spanning unicyclic subgraph, orient its cycle cyclically, and orient all remaining edges away from the cycle. Every vertex has indegree one, while every vertex of has outdegree at most one. The edges directed into therefore form a matching saturating .
If for some there is a colour absent from both and , then recolour vertex to with respect to both and . This requires two recolouring steps in total. Since , inequality (1) applied to yields , a contradiction. Hence
Let denote the number of arcs incident to . The multiset contains colours (counted with multiplicity) appearing in the neighbourhood of . Among them, exactly have colour or , and both colours occur by strong connectivity. So the number of distinct colours in is at most . Thus,
so . Since every vertex of has positive indegree and outdegree,
All inequalities must be equalities. In particular, and for every . This contradicts the statement for , proving the second list-colouring statement.
It remains to finish the case . The equality conditions imply that every has degree two and exactly one incoming and one outgoing arc in . They also imply that for every vertex we have (viewed as a set), and every colour in occurs exactly once in the multiset .
Since is strongly connected and , it contains a directed path with distinct . Write
The unique incoming and outgoing arcs at imply that
Consequently, and it has a unique occurrence in the multiset , namely . In particular, . Similarly, and it has a unique occurrence in the multiset , namely . In particular, .
We now choose some free colour and perform the following six recolourings (three starting from and three starting from ), in the indicated order:
| starting colouring | first | second | third |
Table 1.
The uniqueness properties just established, in particular and , ensure the recolourings at and are allowed. Immediately before the recolouring of , its two neighbours both have colour in the first row and colour in the second, so that recolouring is possible as well. The resulting colourings agree on , and . Applying (1), we obtain the final contradiction .
A sharp upper bound for bipartite graphs
In this section we prove Lemma 6. We restate it for convenience.
Lemma 12. If is bipartite and , then .
Proof. Fix two proper -colourings and a bipartition . Choose any colour . For put
Starting from either colouring , first recolour every vertex of currently coloured to a different available colour. This is possible because at most colours are forbidden by the current neighbours and the old colour . Since is independent, these recolouring steps do not interfere with each other. Next, recolour every vertex of not already coloured to $c. This is allowed because no longer uses , and is independent. The number of recolourings starting from is at most
The two resulting colourings agree on , which is monochromatic in colour . Join them by recolouring each vertex of at most once, while keeping fixed, and then reverse the sequence constructed from . This gives an – recolouring sequence of length at most . Interchanging and gives another such recolouring sequence of length at most . Both constructions use the same arbitrarily chosen colour . Since , we obtain .
Corollary 13. If is bipartite and has a perfect matching, then for every , .
Proof. Take the two colourings obtained by interchanging colours 1 and 2 on the bipartition classes. Every vertex must be recoloured, and for each edge of a maximum matching at least one endpoint must be recoloured twice. This gives the lower bound and Lemma 6 gives the upper bound.
A general lower bound
This section contains the proof of Theorem 7 in a slightly stronger form, namely Theorem 14 below. For , it recovers the known lower bound on the diameter. For , it implies , which is strictly larger than .
As in earlier efforts to prove for several graph classes [15, 37], the high-level idea is to choose a maximum matching and a proper -colouring , and then obtain a new colouring from by interchanging the colours along each edge of , i.e. setting and . Moreover, for every vertex not incident to , a colour distinct from is chosen. If the resulting is also a proper -colouring then we are done: recolouring to requires at least 3 recolouring steps on each edge of , so in total at least recolourings are needed to go from to . The challenge with this approach is that there can be many bad choices of and , for which is not proper. To avoid that difficulty, in the argument below, we instead interchange only a fraction of the vertices, in exchange for a weaker bound.
Theorem 14. Let be a graph with vertices, maximum degree , and matching number . For every integer ,
Proof. Fix a maximum matching and let be the set of vertices that are an endpoint of some edge of . Let be the function that interchanges the endpoints of every edge of . That is, and for every edge of . Define the supergraph of with vertex set , and edges . Note that if and only if . Moreover, has maximum degree at most .
Take a palette of colours equipped with a fixed-point-free involution . That is, is a function such that and for every . We construct a proper colouring of such that
Process the edges of in arbitrary order. When an edge of is reached, each endpoint has at most previously coloured neighbours. Let be the colours on those previously coloured neighbours. Because the previously coloured vertices are the endpoints of some submatching of , the symmetry of and the maintained property (2) on give . Since , we can choose a colour . Then because is an involution, and because has no fixed point. Therefore we properly may extend the colouring to by setting and . This completes the construction of .
For each , consider the set of edges in whose endpoints are coloured and . Since for all , this partitions into disjoint matchings. Put , and let be the union of the largest such matchings. Then
Based on and the colouring , we will now define two proper -colourings. Let be the endpoints of . The restriction of to uses at most colours. Rename these colours into , and let denote the resulting proper -colouring of . As is a supergraph of , is a proper -colouring of as well. On , define . Then is a proper -colouring of , since implies . By construction, and differ at every vertex of , and interchange colours across each edge of .
Extend both colourings to , one new vertex at a time. At a new vertex , choose to avoid its previously assigned neighbours in . Then choose to avoid its previously assigned neighbours in and also to avoid . At most colours are forbidden in the latter step and , so both choices are possible. The resulting proper -colourings differ at every vertex of .
Every sequence from to must change every vertex at least once. On an edge of , the first endpoint to change cannot immediately take its target colour, since that colour is still present at the other endpoint. Hence at least one endpoint of each edge of needs to be recoloured at least twice, so in total at least recolouring steps are needed. The bound on proves the result.
Extension to hypergraphs
We end with a rather different topic, namely an extension to hypergraphs. These results were proved in 2024. The original plan was to write a separate paper about it. To prevent eternal procrastination, we present it here. Given a hypergraph , and a vertex , let denote the maximum integer such that there are hyperedges such that for all , and for all . In other words, is the maximum number of hyperedges containing that are pairwise vertex-disjoint outside . We can think of as the effective degree of . Let denote the maximum effective degree. A (proper) -colouring of is a mapping such that no hyperedge is monochromatic. The chromatic number of is the smallest integer admitting a proper -colouring. Given an integer , the -reconfiguration graph of is the graph whose vertices are the proper -colourings of , any two of which are adjacent if and only if they differ on precisely one vertex. Note that is non-empty if and only if . Throughout this section we assume that the hypergraph is loopless: every hyperedge of contains at least two vertices, so that . We show that for such hypergraphs, the diameter of is also linear in .
Lemma 15. Let be a loopless hypergraph on vertices and let . Then
Proof. We first observe that at most colours are forbidden at any vertex . Indeed, suppose there are distinct colours such that assigning colour to renders some hyperedge monochromatic in , for every . Then whenever , since any vertex in their intersection other than would have to receive both colours and . Thus .
The lower bound is immediate: take any -colouring and permute the set of colours to obtain another -colouring such that for every vertex . Since each vertex needs to be recoloured at least once, at least recolourings are required.
For the upper bound, consider two proper -colourings and . We describe a procedure that transforms into , writing for the current colouring. Call a colour completed if . Initially, . Unless , there exists an uncompleted colour such that . Indeed, every completed colour satisfies . If every uncompleted colour satisfied the strict reverse of the desired inequality, summing over all colours would contradict .
We now perform one phase of the procedure. First, iteratively recolour every vertex currently coloured to an available colour distinct from . By the initial observation and , such a colour always exists. Once there are no vertices with colour anymore, proceed with recolouring every vertex in with . The latter recolourings are allowed in arbitrary order, since contains no hyperedge. By the choice of , this phase requires at most recolouring steps, and it makes completed.
Every previously completed colour remains completed. Indeed, the vertices of have colour throughout the phase: they are neither vertices initially coloured nor vertices whose target colour is . Thus each phase increases the number of completed colours, and no completed colour is ever selected in a later phase. Repeating the procedure therefore eventually makes every colour completed, at which point . Since each colour is selected at most once and a phase selecting uses at most recolourings, the total number of recolourings is at most . If some colour with non-empty is never selected, its contribution is omitted from the sum, saving at least two steps. Otherwise, in the final phase when the last colour is selected, every vertex outside already has its target colour. Then we can recolour directly to in at most steps, saving at least one step. □
Since hypergraphs can be used to represent a wide variety of combinatorial structures, it is clear that Lemma 15 has many corollaries. As an illustration, we mention two of them.
A vertex-colouring of a digraph is acyclic if there is no monochromatic directed cycle. We are interested in the reconfiguration graph whose vertices are the acyclic colourings, two of which adjacent iff they differ on precisely one vertex. Let . For oriented graphs, Picasarri-Arrieta [35 Corollary 11] proved that the reconfiguration graph of acyclic -colourings has diameter at most , provided and . For arbitrary digraphs that bound is false. But with one additional allowed colour, the following gives a stronger bound for arbitrary digraphs.
Corollary 16. Let be a digraph with vertices and let be at least . Then the diameter of the reconfiguration graph of acyclic -colourings of lies between and .
Proof. Choose the hypergraph with vertex set , and with a hyperedge if and only if is the vertex set of a directed cycle in . Every collection of directed cycles that contain a vertex but are disjoint outside implies the existence of disjoint pairs , where (respectively ) is an ingoing (respectively outgoing) edge incident to . Therefore we have , for every vertex . □
The vertex arboricity of a graph is the minimum number of colours in a vertex-colouring such that every monochromatic induced subgraph is a forest. Chartrand, Kronk and Wall [19] showed that . This also follows from Lovász’s decomposition theorem [33]. By taking one colour more, we get the reconfiguration analogue.
Corollary 17. Let be an -vertex graph and let . Then the reconfiguration graph of -colourings of such that every monochromatic induced subgraph is a forest has diameter between and .
Proof. Choose the hypergraph on whose hyperedges are the vertex sets of cycles in . Since for every vertex , there are at most cycles containing while being pairwise disjoint outside , it follows that .
Let be the least integer such that has the same (finite) value for every . We call this eventual value the stable diameter of , and the stability threshold. It is not hard to see that the stability threshold is finite. For graphs we know the stable diameter is , by Proposition 2.(i). This suggests a wider research program:
Question 18. Given a hypergraph, what are its stable diameter and stability threshold?
Open problems
While we have disproved all three variants in Conjecture 1, it raises more questions than answers. How does the diameter of the reconfiguration graph behave near the connectivity threshold ? Is there an elegant function that describes it for all graphs, or is the reality much more jagged and littered with exceptions? Which other graph invariants could play a role? Below, we propose some explicit problems for further research, some of which have been posed before.
Echoing the final question from [15]: what is the smallest such that for every graph ? By Theorem 3 and Proposition 2, we know that .
Conversely, what is the largest such that for every graph ? By Theorem 7 and Proposition 2, we know that . In [15] it was asked whether .
What is the smallest integer such that is strictly larger than for some graph with maximum degree ? The same can be asked with a restriction to -regular graphs. In both cases we currently know via Theorems 3 and 4 that .
Given a positive integer , what is the smallest integer such that for all and all graphs with maximum degree ? In other words, what is the stability threshold such that the diameter settles on the stable diameter for all ? We presently know that for all due to De Meyer [26] but for all even due to Theorem 3. Moreover, for all due to [15], which is sharp for . For , with some care the upper bound proof can be adapted to yield . In summary, for infinitely many .
Classify the graph classes for which the diameter of the -colouring reconfiguration graph is exactly equal to , for all . Is there a characterization in terms of forbidden induced subgraphs? If equality fails for a certain class, what is then the optimal bounding function in terms of and ? Other natural graph classes that come to mind are (outer)planar graphs.
Analogous questions can be asked for the list colouring and correspondence colouring variants described in [15]. In addition, Conjecture 4 in [15] is still open, concerning list colouring reconfiguration for graphs with bounded maximum average degree.
The main initial motivation for Conjecture 1 was a weaker one: is , for every graph ? At the time we were inspired by an argument for complete graphs of Bonamy and Bousquet [3 Lemma 5] which was later developed further into the Optimal Renaming Lemma [17]. De Meyer [26] proved it is true for all complete multipartite and all subcubic graphs (compare Proposition 2), and it also holds for all bipartite graphs by Lemma 6. Is it true in general? If so, it is sharp for more than one reason: diameter is attained by both and . In terms of only the number of vertices, the current best upper bound (valid for every value of ) is , from [15 Corollary 9]. Since the refinements in Conjecture 1 have now been disproved, we emphasize and explicitly state our (together with Cambie and Cranston) original motivating conjecture.
Conjecture 19. Let be a graph. If , then .
Declaration of AI use
Yes and no.
Declaration of AI use, expanded
The paper is a balanced recombination of human and AI-assisted (partial) proofs, both old and new, that went through dozens of iterations of alternating human and AI-assisted improvements, simplifications and rewriting. The result is a blurry symbiotic mix.
References
- [1][AKMZ25] Shamil Asgarlı, Sara Krehbiel, Simon MacLean, and Gjergji Zaimi (2025). Extremal diameters of 3-coloring graphs of trees. arXiv:2512.03789. ↑1arxiv.org/abs/2512.03789
- [2][BB13] Marthe Bonamy and Nicolas Bousquet (2013). Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics 44, 257–262. ↑1
- [3][BB18] Marthe Bonamy and Nicolas Bousquet (2018). Recoloring graphs via tree decompositions. European Journal of Combinatorics 69, 200–213. ↑1, 2, 13arxiv.org/abs/1403.6386
- [5][BBH21] Valentin Bartier, Nicolas Bousquet, and Marc Heinrich (2021). Recoloring graphs of treewidth 2. Discrete Mathematics 344(12), 112553. ↑1arxiv.org/abs/2012.11459
- [6][BBP21] Marthe Bonamy, Nicolas Bousquet, and Guillem Perrarnau (2021). Frozen (Δ + 1)-colourings of bounded degree graphs. Combinatorics, Probability and Computing 30(3), 330–343. ↑2DOI
- [7][BC25] Manoj Belavadi and Kathie Cameron (2025). Recoloring some hereditary graph classes. Discrete Applied Mathematics 361, 389–401. ↑2DOI
- [8][BCH25] Manoj Belavadi, Kathie Cameron, and Elias Hildred (2025). Frozen colourings in 2K₂-free graphs. Electronic Journal of Combinatorics 32(2), P2.29. ↑2
- [9]Manoj Belavadi, Kathie Cameron, and Owen Merkel (2024). Reconfiguration of vertex colouring and forbidden induced subgraphs. European Journal of Combinatorics 118, 103908. ↑2DOI
- [11]Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie (2025). Short and local transformations between (Δ + 1)-colorings. Innovations in Graph Theory 2, 119–156. ↑2
- [12]Nicolas Bousquet and Marc Heinrich (2022). A polynomial version of Cereceda’s conjecture. Journal of Combinatorial Theory, Series B 155, 1–16. ↑1arxiv.org/abs/1903.05619
- [13]Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, and Daniël Paulusma (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27(1), 132–143. ↑2
- [14]Nicolas Bousquet and Guillem Perarnau (2016). Fast recoloring of sparse graphs. European Journal of Combinatorics 52, 1–11. ↑1arxiv.org/abs/1411.6997
- [15]Stijn Cambie, Wouter Cames van Batenburg, and Daniel W. Cranston (2024). Optimally reconfiguring list and correspondence colourings. European Journal of Combinatorics 115, 103798. ↑2, 6, 7, 9, 12, 13DOI
- [16]Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Jan van den Heuvel, and Ross J. Kang (2025). Reconfiguration of list colourings. arXiv:2505.08020. ↑2arxiv.org/abs/2505.08020
- [17]Stijn Cambie, Wouter Cames van Batenburg, and Daniel W. Cranston (2026). Sharp bounds on lengths of linear recolouring sequences. Electronic Journal of Combinatorics 33(1), P1.18. ↑1, 13arxiv.org/abs/2412.19695
- [18]Luis Cereceda (2007). Mixing graph colourings. Ph.D. thesis, London School of Economics and Political Science. ↑2
- [19]Gary Chartrand, Hudson V. Kronk, and Curtiss E. Wall (1968). The point-arboricity of a graph. Israel Journal of Mathematics 6, 169–175. ↑12DOI
- [21]Daniel W. Cranston (2022). List-recoloring of sparse graphs. European Journal of Combinatorics 105, 103562. ↑1arxiv.org/abs/2201.05133
- [24]Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda (2006). Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures & Algorithms 29(4), 450–465. ↑1DOI
- [26][DM26] Lucas De Meyer (2026). Optimal list recoloring of subcubic graphs and complete multipartite graphs. Discrete Mathematics 349(8), 115155. ↑2, 12, 13DOI
- [27][Feg21] Carl Feghali (2021). Reconfiguring colorings of graphs with bounded maximum average degree. Journal of Combinatorial Theory, Series B 147, 133–138. ↑1arxiv.org/abs/1904.12698
- [28][FJP16] Carl Feghali, Matthew Johnson, and Daniël Paulusma (2016). A reconfigurations analogue of Brooks’ theorem and its consequences. Journal of Graph Theory 83(4), 340–358. ↑2arxiv.org/abs/1501.05800
- [30][Heu13] Ian van den Heuvel (2013). The complexity of change. Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, vol. 409 (edited by Simon R. Blackburn, Stefanie Gerke, and Mark Wildon), 127–160. ↑1
- [31][Jer95] Mark Jerrum (1995). A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms 7(2), 157–165. ↑2DOI
- [33][Lov66] László Lovász (1966). On decomposition of graphs. Studia Scientiarum Mathematicarum Hungarica 1, 237–238. ↑12
- [34][Nis18] Naomi Nishimura (2018). Introduction to reconfiguration. Algorithms 11(4), 52. ↑1DOI
- [35][PA24] Lucas Picasarri-Arrieta (2024). Strengthening the directed Brooks’ theorem for oriented graphs and consequences on digraph recolouring. Journal of Graph Theory 106(1), 5–22. ↑11
- [36][WL26] Yichen Wang and Mei Lu (2026). Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs. Discrete Mathematics 349(7), 115055. ↑1arxiv.org/abs/2509.15456
- [37][Zev23] K. B. Zeven (2023). Reconfiguration of graph colorings. Bachelor’s thesis, Delft University of Technology. ↑2, 9
