Δ-List vertex coloring in linear time

We give a new proof of a theorem of Erdős, Rubin, and Taylor. Our proof yields the first linear time algorithm to Δ-list-color any graph containing no (Δ+1)-clique, and containing no odd cycle if Δ=2. Without change, our algorithm can also be used to Δ-color such graphs. It has the same resource bound as, but is simpler than, the current known algorithm of Lovász for Δ-coloring such graphs.