Graphs whose choice number is equal to their chromatic number
Graphs whose choice number is equal to their chromatic number
复制标题
DOI：
10.1002/(sici)1097-0118(199802)27:2
复制
发表时间：
1998-02
期刊：
影响因子：
--
通讯作者：
Sylvain Gravier;Frédéric Maffray
中科院分区：
文献类型：
--
作者：
Sylvain Gravier;Frédéric Maffray
一个图G是k-可选的，如果它允许顶点染色，只要每个顶点允许的颜色被限制在一个长度为k的列表中。如果X表示G的通常色数，我们关心的是哪种G是X-可选的。这个问题包含了一个著名的猜想，即每个线图都是X-可选的。我们提出了一些其他类的图是X-choosable的，所有这些类都与无爪图。John Wiley & Sons，Inc. J Graph Theory 27：8797，1998
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 X denotes the usual chromatic number of G, we are interested in which kind of G is X-choosable. This question contains a famous conjecture, which states that every line-graph is X-choosable. We present some other classes of graphs that are X-choosable; all these classes are related to claw-free graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 8797, 1998