Premium
On a list coloring conjecture of Reed
Author(s) -
Bohman Tom,
Holzman Ron
Publication year - 2002
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.10054
Subject(s) - combinatorics , mathematics , conjecture , list coloring , fractional coloring , complete coloring , vertex (graph theory) , graph coloring , edge coloring , brooks' theorem , graph , degree (music) , discrete mathematics , 1 planar graph , graph power , chordal graph , line graph , physics , acoustics
We construct graphs with lists of available colors for each vertex, such that the size of every list exceeds the maximum vertex‐color degree, but there exists no proper coloring from the lists. This disproves a conjecture of Reed. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 106–109, 2002