In the mathematics of

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of

sparse graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...

s. It states that, for two different colorings of a graph of

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

, both using at most 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

of an undirected graph is the smallest number such that every non-empty subgraph of has at least one vertex of degree at most . If one repeatedly removes a minimum-degree vertex from until no vertices are left, then the largest of the degrees of the vertices at the time of their removal will be exactly , and this method of repeated removal can be used to compute the degeneracy of any graph in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

Greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...

the vertices in the reverse of this removal ordering will automatically produce a coloring with at most colors, and for some graphs (such as

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

s and odd-length

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s) this number of colors is optimal. For colorings with 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 A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

(the graphs of degeneracy 1) or between -colorings of a complete graph in this way; their colorings are said to be frozen. Cycle graphs of length other than four also have disconnected families of -colorings., p. 37. However, with one additional color, using colorings with 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 In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

on the space of -colorings, using moves of this type, is mixing. This means that the random walk will eventually converge to the

discrete uniform distribution In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein a finite number of values are equally likely to be observed; every one of ''n'' values has equal probability 1/''n''. Anothe ...

on these colorings as its

steady state In systems theory, a system or a Process theory, process is in a steady state if the variables (called state variables) which define the behavior of the system or the process are unchanging in time. In continuous time, this means that for those p ...

, 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 In statistical physics, Glauber dynamics is a way to simulate the Ising model (a model of magnetism) on a computer. It is a type of Markov Chain Monte Carlo algorithm. The algorithm In the Ising model, we have say N particles that can spin up ...

Statement

The fact that the Glauber dynamics converges to the uniform distribution on -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 In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

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 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 , 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 -colorings of -degenerate graphs. On the other hand, he proved that the diameter of the color space is at most quadratic (or, in

big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...

, ) for colorings that use at least 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". 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 , and for -colorings of these graphs, the diameter of the space of colorings is . If true, this would be best possible, as the space of 3-colorings of a

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...

has quadratic diameter.

Partial and related results

Although Cereceda's conjecture itself remains open even for degeneracy , it is known that for any fixed value of the diameter of the space of -colorings is polynomial (with a different polynomial for different values of ). More precisely, the diameter is . When the number of colorings is at least , the diameter is quadratic. A related question concerns the possibility that, for numbers of colors greater than , the diameter of the space of colorings might decrease from quadratic to linear. suggest that this might be true whenever the number of colors is at least . The Glauber dynamics is not the only way to change colorings of graphs into each other. Alternatives include the Kempe dynamics in which one repeatedly finds and swaps the colors of

Kempe chain Kempe may refer to: * Kempe baronets, a title in the Baronetage of England * Kempe chain, part of the four-colour theorem * Kempe Fjord, King Christian X Land, Greenland * Kempe Glacier, Antarctica * Kempe Hill, former name of Camp Hill, West Mid ...

s, and the "heat bath" dynamics in which one chooses pairs of adjacent vertices and a valid recoloring of that pair. Both of these kinds of moves include the Glauber one-vertex moves as a special case, as changing the color of one vertex is the same as swapping the colors on a Kempe chain that only includes that one vertex. These moves may have stronger mixing properties and lower diameter of the space of colorings. For instance, both the Kempe dynamics and the heat bath dynamics mix rapidly on 3-colorings of cycle graphs, whereas the Glauber dynamics is not even connected when the length of the cycle is not four.

References

{{reflist, refs= {{citation , 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 {{citation , 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 The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, 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 {{citation , last1 = Bousquet , first1 = Nicolas , last2 = Heinrich , first2 = Marc , arxiv = 1903.05619 , title = A polynomial version of Cereceda's conjecture , year = 2019 {{citation , 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. See in particular Theorem 11, page 141. {{citation, title=Mixing graph colourings, first=Luis, last=Cereceda, series=doctoral dissertation, publisher=London School of Economics, year=2007, url=http://etheses.lse.ac.uk/131/. See especially page 109. {{citation , 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. See in particular Lemma 2 of this paper, and {{harvtxt, Cereceda, 2007, Theorem 2.7, p. 26. {{citation , last1 = Eiben , first1 = Eduard , last2 = Feghali , first2 = Carl , arxiv = 1810.00731 , title = Towards Cereceda's conjecture for planar graphs , year = 2018 {{citation , last1 = Matula , first1 = David W. , author1-link = David Matula , last2 = Beck , first2 = L. L. , doi = 10.1145/2402.322385 , journal =

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...

, volume = 30 , mr = 0709826 , number = 3 , pages = 417–427 , title = Smallest-last ordering and clustering and graph coloring algorithms , year = 1983 Conjectures Graph coloring Reconfiguration