Premium
A lower bound for partial list colorings
Author(s) -
Chappell Glenn G.
Publication year - 1999
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/(sici)1097-0118(199912)32:4<390::aid-jgt6>3.0.co;2-d
Subject(s) - combinatorics , mathematics , corollary , conjecture , colored , vertex (graph theory) , chromatic scale , upper and lower bounds , list coloring , graph , discrete mathematics , graph power , line graph , mathematical analysis , materials science , composite material
Let G be an n ‐vertex graph with list‐chromatic number χ ℓ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /χ ℓ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least ${6}\over{7}$ of the conjectured number can be colored. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 390–393, 1999