Reconfiguring 10-colourings of planar graphs (Q2657051)

In this paper, the author considers finite, undirected graphs that do not contain loops or parallel edges. For an integer \(d\geq 1\), a graph \(G=(V, E)\) is called \(d\)-degenerate if every subgraph of \(G\) has minimum degree at most \(d\). Trees and planar graphs are examples of \(1\)-degenerate and 5-degenerate graphs, respectively. For an integer \(k\geq 1\) and a graph \(G=(V,E)\), a function \(c:V\rightarrow \{1,\dots,k\}\) is called a \(k\)-coloring of \(G\) if for any edge \(e=uv\in E\), we have \(c(u)\neq c(v)\). Let \(R_k(G)\) be a graph, whose vertices are all \(k\)-colorings of \(G\), and two \(k\)-colorings of \(G\) form an edge in \(R_k(G)\) if and only if they differ only on color of exactly one vertex. The main result of the paper is the following: Theorem: \(R_{10}(G)\) has diameter at most \(\frac{n(n+1)}{2}\) for all planar graphs \(G\) on \(n\) vertices. The result of the author deals with a conjecture of \textit{L. Cereceda} [Mixing graph colourings. London: London School of Economics (PhD Thesis) (2007)], which states that for \(l\geq k+2\) and every \(k\)-degenerate graph on \(n\) vertices \(R_{l}(G)\) has diameter \(O(n^2)\).