Reconfiguring 10-Colourings of Planar Graphs
- PDF / 222,136 Bytes
- 4 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 162 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Reconfiguring 10-Colourings of Planar Graphs Carl Feghali1 Received: 16 October 2019 / Revised: 22 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract 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 nðn þ 1Þ=2. Since planar graphs are 5-degenerate, this affirms Cereceda’s conjecture for planar graphs in the case ‘ ¼ 2k. Keywords Graph colouring Reconfiguration graph Planar graph
1 Introduction and Result 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 the colour of exactly one vertex of G. A list assignment of a graph is a function L that assigns to each vertex v a list L(v) of colours. The graph G is L-colourable if it has a proper colouring f such that f ðvÞ 2 LðvÞ for each vertex v of G. For a positive integer d, a graph G is d-degenerate if every subgraph of G contains a vertex of degree at most d. Expressed in another way, G is ddegenerate if there there exists an ordering v1 ; . . .; vn of the vertices in G such that each vi has at most d neighbours vj with j\i. Reconfiguration problems have received much attention in the past decade; we refer the reader to the surveys by van den Heuvel [15] and Nishimura [12]. & Carl Feghali [email protected] 1
Computer Science Institute of Charles University, Prague, Czech Republic
123
Graphs and Combinatorics
In this note, we are concerned with a conjecture of Cereceda [4] from 2007 which asserts that for every integer ‘ k þ 2 and k-degenerate graph G on n vertices, R‘ ðGÞ has diameter Oðn2 Þ. Cereceda [4] verified the conjecture whenever ‘ 2k þ 1 but the conjecture remains open for every other value 2k ‘ k þ 2. It is also known to hold if degeneracy is replaced by tree-width [1] (a shorter proof with a weaker bound is proposed in [8]) as well as for ðD 1Þ-degenerate graphs [11], where D is the maximum degree of the graph under consideration. Our aim in this note is to address the conjecture for planar graphs in the following theorem. Theorem 1 For every planar graph G on n vertices, R10 ðGÞ has diameter at most nðn þ 1Þ=2. Since planar graphs are 5-degenerate, Theorem 1 affirms Cereceda’s conjecture for planar graphs in the case ‘ ¼ 2k. In all other cases, some partial results are known. Given a planar graph G on n vertices, it is shown in [3] that R‘ ðGÞ has diameter Oðnc Þ for each ‘ 8 and some (large) positive constant c (see [9] for a short proof of thi
Data Loading...
