research-article

A polynomial version of Cereceda's conjecture

Authors:

Nicolas Bousquet,

Marc HeinrichAuthors Info & Claims

Volume 155, Issue C

Pages 1 - 16

https://doi.org/10.1016/j.jctb.2022.01.006

Published: 01 July 2022 Publication History

Abstract

Let k and d be positive integers such that k ≥ d + 2. Consider two k-colourings of a d-degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper colouring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length.

The k-reconfiguration graph of G is the graph whose vertices are the proper k-colourings of G, with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the ( d + 2 )-reconfiguration graph of any d-degenerate graph on n vertices is O ( n 2 ). So far, there is no proof of a polynomial upper bound on the diameter, even for d = 2.

In this paper, we prove that the diameter of the k-reconfiguration graph of a d-degenerate graph is O ( n d + 1 ) for k ≥ d + 2. Moreover, we prove that if k ≥ 3 2 ( d + 1 ) then the diameter of the k-reconfiguration graph is quadratic, improving the previous bound of k ≥ 2 d + 1. We also show that the 5-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.

References

[1]

H.-J. Böckenhauer, E. Burjons, M. Raszyk, P. Rossmanith, Reoptimization of parameterized problems, arXiv e-prints, 2018.

[2]

M. Bonamy, N. Bousquet, Recoloring graphs via tree decompositions, Eur. J. Comb. 69 (2018) 200–213.

[3]

M. Bonamy, N. Bousquet, C. Feghali, M. Johnson, On a conjecture of Mohar concerning Kempe equivalence of regular graphs, J. Comb. Theory, Ser. B 135 (2019) 179–199.

[4]

M. Bonamy, N. Bousquet, G. Perarnau, Frozen ( Δ + 1 )-colourings of bounded degree graphs, Comb. Probab. Comput. 30 (3) (2021) 330–343.

[5]

M. Bonamy, M. Johnson, I. Lignos, V. Patel, D. Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J. Comb. Optim. (2012) 1–12.

[6]

P. Bonsma, L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theor. Comput. Sci. 410 (50) (2009) 5215–5226.

[7]

P. Bose, A. Lubiw, V. Pathak, S. Verdonschot, Flipping edge-labelled triangulations, Comput. Geom. 68 (2018) 309–326.

[8]

N. Bousquet, G. Perarnau, Fast recoloring of sparse graphs, Eur. J. Comb. 52 (2016) 1–11.

[9]

L. Cereceda, Mixing Graph Colourings, PhD thesis London School of Economics and Political Science, 2007.

[10]

L. Cereceda, J. van den Heuvel, M. Johnson, Mixing 3-colourings in bipartite graphs, Eur. J. Comb. 30 (7) (2009) 1593–1606.

[11]

L. Cereceda, J. van den Heuvel, M. Johnson, Finding paths between 3-colorings, J. Graph Theory 67 (1) (2011) 69–82.

[12]

S. Chen, M. Delcourt, A. Moitra, G. Perarnau, L. Postle, Improved bounds for randomly sampling colorings via linear programming, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 2019, pp. 2216–2234.

[13]

R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, third edition, Springer-Verlag, Heidelberg, 2005.

[14]

M. Dyer, A.D. Flaxman, A.M. Frieze, E. Vigoda, Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Struct. Algorithms 29 (4) (2006) 450–465.

[15]

E. Eiben, C. Feghali, Toward cereceda's conjecture for planar graphs, J. Graph Theory (2019).

[16]

C. Feghali, Paths between colourings of sparse graphs, Eur. J. Comb. 75 (2019) 169–171.

[17]

C. Feghali, Reconfiguring 10-colourings of planar graphs, arXiv e-prints, 2019.

[18]

C. Feghali, M. Johnson, D. Paulusma, A reconfigurations analogue of Brooks' theorem and its consequences, J. Graph Theory 83 (4) (2016) 340–358.

[19]

A. Frieze, E. Vigoda, A survey on the use of Markov chains to randomly sample colourings, Oxf. Lect. Ser. Math. Appl. 34 (2007) 53.

[20]

B. Mohar, J. Salas, On the non-ergodicity of the Swendsen–Wang–Kotecký algorithm on the Kagomé lattice, J. Stat. Mech. Theory Exp. 2010 (05) (2010).

[21]

N. Nishimura, Introduction to reconfiguration, Algorithms 11 (4) (2018) 52.

[22]

J. van den Heuvel, The complexity of change, p. 409 in: S.R. Blackburn, S. Gerke, M. Wildon (Eds.), Part of London Mathematical Society Lecture Note Series, 2013.

Cited By

Cambie SCames van Batenburg WCranston D(2024)Optimally reconfiguring list and correspondence colouringsEuropean Journal of Combinatorics10.1016/j.ejc.2023.103798115:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.ejc.2023.103798

Index Terms

A polynomial version of Cereceda's conjecture
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
2. Theory of computation
  1. Randomness, geometry and discrete structures

Index terms have been assigned to the content through auto-classification.

Recommendations

A step towards the strong version of Havel's three color conjecture

In 1970, Havel asked if each planar graph with the minimum distance, d^@?, between triangles large enough is 3-colorable. There are 4-chromatic planar graphs with d^@?=3 (Aksenov, Mel@?nikov, and Steinberg, 1980). The first result in the positive ...
The Erdős-Hajnal conjecture for rainbow triangles

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ( n 1 / 3 log 2 n ) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a ...
Reducing Hajós' 4-coloring conjecture to 4-connected graphs

Hajós conjectured that, for any positive integer k, every graph containing no K_k+1-subdivision is k-colorable. This is true when k ≤ 3, and false when k ≥ 6. Hajós' conjecture remains open for k = 4, 5. In this paper, we show that any possible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B

Journal of Combinatorial Theory Series B Volume 155, Issue C

Jul 2022

389 pages

ISSN:0095-8956

Issue’s Table of Contents

Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 July 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cambie SCames van Batenburg WCranston D(2024)Optimally reconfiguring list and correspondence colouringsEuropean Journal of Combinatorics10.1016/j.ejc.2023.103798115:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.ejc.2023.103798

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents