10-list Recoloring of Planar Graphs

Abstract

Fix a planar graph $G$ and a list-assignment $L$ with $|L(v)|=10$ for all $v\in V(G)$. Let $\alpha$ and $\beta$ be $L$-colorings of $G$. A recoloring sequence from $\alpha$ to $\beta$ is a sequence of $L$-colorings, beginning with $\alpha$ and ending with $\beta$, such that each successive pair in the sequence differs in the color on a single vertex of $G$. We show that there exists a constant $C$ such that for all choices of $\alpha$ and $\beta$ there exists a recoloring sequence $\sigma$ from $\alpha$ to $\beta$ that recolors each vertex at most $C$ times. In particular, $\sigma$ has length at most $C|V(G)|$. This confirms a conjecture of Dvořák and Feghali. For our proof, we introduce a new technique for quickly showing that many configurations are reducible. We believe this method may be of independent interest and will have application to other problems in this area.

20 pages, 16 figures; 2nd version incorporates reviewer feedback; to appear in European J. Combinatorics