Back to Search Start Over

An update on reconfiguring $10$-colorings of planar graphs

Authors :
Dvořák, Zdeněk
Feghali, Carl
Publication Year :
2020

Abstract

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.<br />Comment: 25 pages, 1 figure

Subjects

Subjects :
Mathematics - Combinatorics
05C15

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2002.05383
Document Type :
Working Paper