Cereceda's conjecture

Last updated September 26, 2024 • 5 min readFrom Wikipedia, The Free Encyclopedia

Unsolved problem in mathematics:

Can every two

(d+2)

-colorings of a

d

-degenerate graph be transformed into each other by quadratically many steps that change the color of one vertex at a time?

(more unsolved problems in mathematics)

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 $d$ , both using at most $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 $G$ is the smallest number $d$ such that every non-empty subgraph of $G$ has at least one vertex of degree at most $d$ . If one repeatedly removes a minimum-degree vertex from $G$ until no vertices are left, then the largest of the degrees of the vertices at the time of their removal will be exactly $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 $d + 1$ colors, and for some graphs (such as complete graphs and odd-length cycle graphs) this number of colors is optimal.^[1]

For colorings with $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 $(d + 1)$ -colorings of a complete graph in this way; their colorings are said to be frozen.^[2] Cycle graphs of length other than four also have disconnected families of $(d + 1)$ -colorings.^[3] However, with one additional color, using colorings with $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 $(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.^[4]

Statement

The fact that the Glauber dynamics converges to the uniform distribution on $(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 $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 $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 $(d + 1)$ -colorings of $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, $O (n 2)$ ) for colorings that use at least $2 d + 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".^[5]

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 $d$ , and for $(d + 2)$ -colorings of these graphs, the diameter of the space of colorings is $O (n 2)$ .^[6]^[7]^[8]^[9] If true, this would be best possible, as the space of 3-colorings of a path graph has quadratic diameter.^[10]

Partial and related results

Although Cereceda's conjecture itself remains open even for degeneracy $d = 2$ , it is known that for any fixed value of $d$ the diameter of the space of $(d + 2)$ -colorings is polynomial (with a different polynomial for different values of $d$ ). More precisely, the diameter is $O (n d + 1)$ . When the number of colors is at least $(3 d + 3)/2$ , the diameter is quadratic.^[7]

A related question concerns the possibility that, for numbers of colors greater than $d + 2$ , the diameter of the space of colorings might decrease from quadratic to linear.^[7] Bousquet & Bartier (2019) suggest that this might be true whenever the number of colors is at least $d + 3$ .^[9]

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 chains,^[8] 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.

Related Research Articles

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary of non-zero length. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubts remain.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

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 of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

<span class="mw-page-title-main">Thue number</span>

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after mathematician Axel Thue, who studied the squarefree words used to define this number.

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 and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges. Alfred Errera published it in 1921 as a counterexample to Kempe's erroneous proof of the four color theorem; it was named after Errera by Hutchinson & Wagon (1998).

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

The Earth–Moon problem is an unsolved problem on graph coloring in mathematics. It is an extension of the planar map coloring problem, and was posed by Gerhard Ringel in 1959. An intuitive form of the problem asks how many colors are needed to color political maps of the Earth and Moon, in a hypothetical future where each Earth country has a Moon colony which must be given the same color. In mathematical terms, it seeks the chromatic number of biplanar graphs. It is known that this number is at least 9 and at most 12.

References

↑ Matula, David W.; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms", Journal of the ACM , 30 (3): 417–427, doi: 10.1145/2402.322385 , MR 0709826, S2CID 4417741
↑ See Cereceda (2007), remark following Proposition 2.6, p. 26.
↑ Cereceda (2007), p. 37.
↑ Dyer, Martin; Flaxman, Abraham D.; Frieze, Alan M.; Vigoda, Eric (2006), "Randomly coloring sparse random graphs with fewer colors than the maximum degree", Random Structures & Algorithms, 29 (4): 450–465, doi:10.1002/rsa.20129, MR 2268231, S2CID 5342223 . See in particular Lemma 2 of this paper, and Cereceda (2007), Theorem 2.7, p. 26.
↑ Cereceda, Luis (2007), Mixing graph colourings (phd), doctoral dissertation, London School of Economics. See especially page 109.
↑ Eiben, Eduard; Feghali, Carl (2018), Towards Cereceda's conjecture for planar graphs, arXiv: 1810.00731
1 2 3 Bousquet, Nicolas; Heinrich, Marc (2019), A polynomial version of Cereceda's conjecture, arXiv: 1903.05619
1 2 Bonamy, Marthe; Bousquet, Nicolas; Feghali, Carl; Johnson, Matthew (2019), "On a conjecture of Mohar concerning Kempe equivalence of regular graphs", Journal of Combinatorial Theory , Series B, 135: 179–199, arXiv: 1510.06964 , doi: 10.1016/j.jctb.2018.08.002 , MR 3926265, S2CID 5465047
1 2 Bousquet, Nicolas; Bartier, Valentin (2019), "Linear transformations between colorings in chordal graphs", in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, LIPIcs, vol. 144, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 24:1–24:15, doi: 10.4230/LIPIcs.ESA.2019.24 , ISBN 9783959771245, S2CID 195791634
↑ Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël (2014), "Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs" (PDF), Journal of Combinatorial Optimization, 27 (1): 132–143, doi:10.1007/s10878-012-9490-y, MR 3149109, S2CID 254648357 . See in particular Theorem 11, page 141.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[mb-1] Matula, David W.; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms", Journal of the ACM , 30 (3): 417–427, doi: 10.1145/2402.322385 , MR 0709826, S2CID 4417741

[2] See Cereceda (2007), remark following Proposition 2.6, p. 26.

[3] Cereceda (2007), p. 37.

[dffv-4] Dyer, Martin; Flaxman, Abraham D.; Frieze, Alan M.; Vigoda, Eric (2006), "Randomly coloring sparse random graphs with fewer colors than the maximum degree", Random Structures & Algorithms, 29 (4): 450–465, doi:10.1002/rsa.20129, MR 2268231, S2CID 5342223 . See in particular Lemma 2 of this paper, and Cereceda (2007), Theorem 2.7, p. 26.

[cereceda-5] Cereceda, Luis (2007), Mixing graph colourings (phd), doctoral dissertation, London School of Economics. See especially page 109.

[ef-6] Eiben, Eduard; Feghali, Carl (2018), Towards Cereceda's conjecture for planar graphs, arXiv: 1810.00731

[bh-7] 1 2 3 Bousquet, Nicolas; Heinrich, Marc (2019), A polynomial version of Cereceda's conjecture, arXiv: 1903.05619

[bbfj-8] 1 2 Bonamy, Marthe; Bousquet, Nicolas; Feghali, Carl; Johnson, Matthew (2019), "On a conjecture of Mohar concerning Kempe equivalence of regular graphs", Journal of Combinatorial Theory , Series B, 135: 179–199, arXiv: 1510.06964 , doi: 10.1016/j.jctb.2018.08.002 , MR 3926265, S2CID 5465047

[bb-9] 1 2 Bousquet, Nicolas; Bartier, Valentin (2019), "Linear transformations between colorings in chordal graphs", in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, LIPIcs, vol. 144, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 24:1–24:15, doi: 10.4230/LIPIcs.ESA.2019.24 , ISBN 9783959771245, S2CID 195791634

[bjlpp-10] Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël (2014), "Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs" (PDF), Journal of Combinatorial Optimization, 27 (1): 132–143, doi:10.1007/s10878-012-9490-y, MR 3149109, S2CID 254648357 . See in particular Theorem 11, page 141.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]