Back to Search
Start Over
A polynomial version of Cereceda's conjecture.
- Source :
-
Journal of Combinatorial Theory - Series B . Jul2022, Vol. 155, p1-16. 16p. - Publication Year :
- 2022
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 155
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 156472333
- Full Text :
- https://doi.org/10.1016/j.jctb.2022.01.006