Equitable list coloring of graphs with bounded degree

A graph G is equitably k-choosable if for every k-list assignment L there exists an L-coloring of G such that every color class has at most âŒ̂|G|/k⌉ vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably (r+1)-choosable. In particular, we confirm the conjecture for r≤7 and show that every graph with maximum degree at most r and at least r ³ vertices is equitably (r+2)-choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.