2019/02/06 by Feghali, Carl
#05C15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1902.02278
Let k ≥ 1 be an integer. The reconfiguration graph Rk(G) of the k-colourings of a graph~G has as vertex set the set of all possible k-colourings of G and two colourings are adjacent if they differ on exactly one vertex. A conjecture of Cereceda from 2007 asserts that for every integer ℓ ≥ k + 2 and k-degenerate graph G on n vertices, Rℓ(G) has diameter O(n2). The conjecture has been verified only when ℓ ≥ 2k + 1. We give a simple proof that if G is a planar graph on n vertices, then R10(G) has diameter at most n2. Since planar graphs are 5-degenerate, this affirms Cereceda's conjecture for planar graphs in the case ℓ = 2k.