List-recoloring of sparse graphs

Fix a graph G, a list-assignment L for G, and L-colorings alpha and beta. An L-recoloring sequence, starting from alpha, recolors a single vertex at each step, so that each resulting intermediate coloring is a proper L-coloring. An L-recoloring sequence transforms alpha to beta if its initial coloring is alpha and its final coloring is beta. We prove there exists an L-recoloring sequence that transforms alpha to beta and recolors each vertex at most a constant number of times if (i) G is triangle-free and planar and L is a 7-assignment, or (ii) mad(G) < 17/5 and L is a 6-assignment or (iii) mad(G) < 22/9 and L is a 4-assignment. Parts (i) and (ii) confirm conjectures of Dvorak and Feghali.

Automated summary

This text discusses fixed graphs, list-assignments, and L-colorings, as well as L-recoloring sequences transformation and recoloring issues.