Premium
Graphs whose choice number is equal to their chromatic number
Author(s) -
Gravier Sylvain,
Maffray Frédéric
Publication year - 1998
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(199802)27:2<87::aid-jgt4>3.0.co;2-b
Subject(s) - combinatorics , mathematics , list coloring , vertex (graph theory) , chromatic scale , complete coloring , conjecture , fractional coloring , discrete mathematics , graph coloring , edge coloring , brooks' theorem , graph , line graph , 1 planar graph , graph power
A graph G is k ‐choosable if it admits a vertex‐coloring whenever the colors allowed at each vertex are restricted to a list of length k . If χ denotes the usual chromatic number of G , we are interested in which kind of G is χ‐choosable. This question contains a famous conjecture, which states that every line‐graph is χ‐choosable. We present some other classes of graphs that are χ‐choosable; all these classes are related to claw‐free graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 87–97, 1998