10-list recoloring of planar graphs
Daniel W. Cranston · European Journal of Combinatorics · 2025
Fix a planar graph G and a list assignment L with | L ( v ) | = 10 for all v ∈ 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.