Charles Explorer logo
🇬🇧

A Thomassen-type method for planar graph recoloring

Publication at Faculty of Mathematics and Physics |
2021

Abstract

The reconfiguration graph R-k(G) for the k-colorings of a graph G has as vertices all possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that for a planar graph G with n vertices, R-12(G) has diameter at most 6n, and if G is triangle-free, then R-8(G) has diameter at most 4n.

We use a list coloring technique inspired by results of Thomassen to improve on the number of colors, showing that for a planar graph G with n vertices, R-10(G) has diameter at most 8n, and if G is triangle-free, then R-7(G) has diameter at most 7n. (C) 2021 Elsevier Ltd. All rights reserved.