| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429276 | Information Processing Letters | 2006 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
