Abstrakt
Let 𝑘>=1 be an integer. The reconfiguration graph 𝑅𝑘(𝐺) 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 ℓ>=𝑘+2 and k-degenerate graph G on n vertices, 𝑅ℓ(𝐺) has diameter 𝑂(𝑛2). The conjecture has been verified only when ℓ>=2𝑘+1.
We give a simple proof that if G is a planar graph on n vertices, then 𝑅10(𝐺) has diameter at most 𝑛(𝑛+1)/2. Since planar graphs are 5-degenerate, this affirms Cereceda's conjecture for planar graphs in the case ℓ=2��.