Cereceda's conjecture
{{Short description|Unsolved problem in the mathematics of graph coloring}}
{{unsolved|mathematics|Can every two -colorings of a -degenerate graph be transformed into each other by quadratically many steps that change the color of one vertex at a time?}}
File:Path 3-colorings.svg, which has degeneracy one. The diameter of this space of colorings is four: it takes four steps to get from either of the top two colorings to the bottom one.]]
In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy {{mvar|d}}, both using at most {{math|d + 2}} colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation.
Background
The degeneracy of an undirected graph {{mvar|G}} is the smallest number {{mvar|d}} such that every non-empty subgraph of {{mvar|G}} has at least one vertex of degree at most {{mvar|d}}. If one repeatedly removes a minimum-degree vertex from {{mvar|G}} until no vertices are left, then the largest of the degrees of the vertices at the time of their removal will be exactly {{mvar|d}}, and this method of repeated removal can be used to compute the degeneracy of any graph in linear time. Greedy coloring the vertices in the reverse of this removal ordering will automatically produce a coloring with at most {{math|d + 1}} colors, and for some graphs (such as complete graphs and odd-length cycle graphs) this number of colors is optimal.{{r|mb}}
For colorings with {{math|d + 1}} colors, it may not be possible to move from one coloring to another by changing the color of one vertex at a time. In particular, it is never possible to move between 2-colorings of a forest (the graphs of degeneracy 1) or between {{math|(d + 1)}}-colorings of a complete graph in this way; their colorings are said to be frozen.See {{harvtxt|Cereceda|2007}}, remark following Proposition 2.6, p. 26. Cycle graphs of length other than four also have disconnected families of {{math|(d + 1)}}-colorings.{{harvtxt|Cereceda|2007}}, p. 37.
However, with one additional color, using colorings with {{math|d + 2}} colors, all pairs of colorings can be connected to each other by sequences of moves of this type. It follows from this that an appropriately designed random walk on the space of {{math|(d + 2)}}-colorings, using moves of this type, is mixing. This means that the random walk will eventually converge to the discrete uniform distribution on these colorings as its steady state, in which all colorings have equal probability of being chosen. More precisely, the random walk proceeds by repeatedly choosing a uniformly random vertex and choosing uniformly at random among all the available colors for that vertex, including the color it already had; this process is called the Glauber dynamics.{{r|dffv}}
Statement
The fact that the Glauber dynamics converges to the uniform distribution on {{math|(d + 2)}}-colorings naturally raises the question of how quickly it converges. That is, what is the mixing time? A lower bound on the mixing time is the diameter of the space of colorings, the maximum (over pairs of colorings) of the number of steps needed to change one coloring of the pair into the other. If the diameter is exponentially large in the number {{mvar|n}} of vertices in the graph, then the Glauber dynamics on colorings is certainly not rapidly mixing. On the other hand, when the diameter is bounded by a polynomial function of {{mvar|n}}, this suggests that the mixing time might also be polynomial. In his 2007 doctoral dissertation, Cereceda investigated this problem, and found that (even for connected components of the space of colors) the diameter can be exponential for {{math|(d + 1)}}-colorings of {{mvar|d}}-degenerate graphs. On the other hand, he proved that the diameter of the color space is at most quadratic (or, in big O notation, {{math|O(n2)}}) for colorings that use at least {{math|2d + 1}} colors. He wrote that "it remains to determine" whether the diameter is polynomial for numbers of colors between these two extremes, or whether it is "perhaps even quadratic".{{r|cereceda}}
Although Cereceda asked this question for a range of colors and did not phrase it as a conjecture, by 2018 a form of this question became known as Cereceda's conjecture. This unproven hypothesis is the most optimistic possibility among the questions posed by Cereceda: that for graphs with degeneracy at most {{mvar|d}}, and for {{math|(d + 2)}}-colorings of these graphs, the diameter of the space of colorings is {{math|O(n2)}}.{{r|ef|bh|bbfj|bb}}
If true, this would be best possible, as the space of 3-colorings of a path graph has quadratic diameter.{{r|bjlpp}}
References
{{reflist|refs=
| last1 = Bousquet | first1 = Nicolas
| last2 = Bartier | first2 = Valentin
| editor1-last = Bender | editor1-first = Michael A.
| editor2-last = Svensson | editor2-first = Ola
| editor3-last = Herman | editor3-first = Grzegorz
| contribution = Linear transformations between colorings in chordal graphs
| doi = 10.4230/LIPIcs.ESA.2019.24
| pages = 24:1–24:15
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany
| volume = 144
| year = 2019| doi-access = free
| isbn = 9783959771245
| s2cid = 195791634
}}
| last1 = Bonamy | first1 = Marthe
| last2 = Bousquet | first2 = Nicolas
| last3 = Feghali | first3 = Carl
| last4 = Johnson | first4 = Matthew
| doi = 10.1016/j.jctb.2018.08.002
| journal = Journal of Combinatorial Theory
| mr = 3926265
| pages = 179–199
| series = Series B
| title = On a conjecture of Mohar concerning Kempe equivalence of regular graphs
| url = http://dro.dur.ac.uk/id/document/34436
| volume = 135
| year = 2019| s2cid = 5465047
| doi-access = free
| arxiv = 1510.06964
}}
| last1 = Bousquet | first1 = Nicolas
| last2 = Heinrich | first2 = Marc
| arxiv = 1903.05619
| title = A polynomial version of Cereceda's conjecture
| year = 2019}}
| last1 = Bonamy | first1 = Marthe
| last2 = Johnson | first2 = Matthew
| last3 = Lignos | first3 = Ioannis
| last4 = Patel | first4 = Viresh
| last5 = Paulusma | first5 = Daniël
| doi = 10.1007/s10878-012-9490-y
| issue = 1
| journal = Journal of Combinatorial Optimization
| mr = 3149109
| pages = 132–143
| title = Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
| volume = 27
| year = 2014| s2cid = 254648357
| url = http://dro.dur.ac.uk/10709/1/10709.pdf
}}. See in particular Theorem 11, page 141.
| last1 = Dyer | first1 = Martin
| last2 = Flaxman | first2 = Abraham D.
| last3 = Frieze | first3 = Alan M.
| last4 = Vigoda | first4 = Eric
| doi = 10.1002/rsa.20129
| issue = 4
| journal = Random Structures & Algorithms
| mr = 2268231
| pages = 450–465
| title = Randomly coloring sparse random graphs with fewer colors than the maximum degree
| volume = 29
| year = 2006| s2cid = 5342223
}}. See in particular Lemma 2 of this paper, and {{harvtxt|Cereceda|2007}}, Theorem 2.7, p. 26.
| last1 = Eiben | first1 = Eduard
| last2 = Feghali | first2 = Carl
| arxiv = 1810.00731
| title = Towards Cereceda's conjecture for planar graphs
| year = 2018}}
| last1 = Matula | first1 = David W. | author1-link = David Matula
| last2 = Beck | first2 = L. L.
| doi = 10.1145/2402.322385
| journal = Journal of the ACM
| volume = 30
| mr = 0709826
| number = 3
| pages = 417–427
| title = Smallest-last ordering and clustering and graph coloring algorithms
| year = 1983| s2cid = 4417741 | doi-access = free
}}
}}