Toward Cereceda's conjecture for planar graphs

Abstract: The reconfiguration graph

R_{k} (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 the colour of exactly one vertex. Cereceda conjectured ten years ago that, for every

k

-degenerate graph

G

on

n

vertices,

R_{k + 2} (G)

has diameter

m a t h c a l O (n^{2})

. The conjecture is wide open, with a best known bound of

m a t h c a l O (k^{n})

, even for planar graphs. We improve this bound for planar graphs to

2^{m a t h c a l O (s q r t n)}

. Our proof can be transformed into an algorithm that runs in

2^{m a t h c a l O (s q r t n)}

time.

Recommendations

Cited in

(15)

This page was built for publication: Toward Cereceda's conjecture for planar graphs