Equitable List Coloring of Graphs with Bounded Degree |
| |
Authors: | H. A. Kierstead A. V. Kostochka |
| |
Affiliation: | 1. SCHOOL OF MATHEMATICAL SCIENCES AND STATISTICS, ARIZONA STATE UNIVERSITY, , TEMPE, ARIZONA;2. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS, , URBANA, ILLINOIS;3. INSTITUTE OF MATHEMATICS, , NOVOSIBIRSK, RUSSIA |
| |
Abstract: | 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 vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably ‐choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r3 vertices is equitably ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings. |
| |
Keywords: | equitable coloring list coloring choosable maximum degree |
|
|