Premium
Equitable List Coloring of Graphs with Bounded Degree
Author(s) -
Kierstead H. A.,
Kostochka A. V.
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21710
Subject(s) - combinatorics , mathematics , graph coloring , conjecture , list coloring , discrete mathematics , degree (music) , bounded function , graph , complete coloring , graph power , line graph , mathematical analysis , physics , acoustics
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 3 vertices is equitably ( r + 2 ) ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.