The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph~$G$ has as vertex set the set of all possible proper $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 if $G$ is a planar graph with $n$ vertices, then $R_{12}(G)$ has diameter at most $6n$. We improve on the number of colors, showing that $R_{10}(G)$ has diameter at most $8n$ for every planar graph $G$ with $n$ vertices.
@article{10_37236_9391,
author = {Zden\v{e}k Dvo\v{r}\'ak and Carl Feghali},
title = {An update on reconfiguring 10-colorings of planar graphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9391},
zbl = {1457.05033},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9391/}
}
TY - JOUR
AU - Zdeněk Dvořák
AU - Carl Feghali
TI - An update on reconfiguring 10-colorings of planar graphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9391/
DO - 10.37236/9391
ID - 10_37236_9391
ER -
%0 Journal Article
%A Zdeněk Dvořák
%A Carl Feghali
%T An update on reconfiguring 10-colorings of planar graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9391/
%R 10.37236/9391
%F 10_37236_9391
Zdeněk Dvořák; Carl Feghali. An update on reconfiguring 10-colorings of planar graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9391
