Graphs whose choice number is equal to their chromatic number
Sylvain Gravier, Frédéric Maffray
Abstract
Sylvain Gravier, Frédéric Maffray
Abstract
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
OpenAlex reports 33 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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
Key concepts: Combinatorics, Mathematics, List coloring, Vertex (graph theory), Chromatic scale, Conjecture, Discrete mathematics, Graph coloring