


















Fix a planar graph $G$ and a list-assignment $L$ with $|L(v)|=10$ for all $v\in V(G)$. Let $α$ and $β$ be $L$-colorings of $G$. A recoloring sequence from $α$ to $β$ is a sequence of $L$-colorings, beginning with $α$ and ending with $β$, 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 $α$ and $β$ there exists a recoloring sequence $σ$ from $α$ to $β$ that recolors each vertex at most $C$ times. In particular, $σ$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。