Graphs whose choice number is equal to their chromatic number

被引:2
作者
Gravier, S [1 ]
Maffray, F [1 ]
机构
[1] CNRS, Lab Leibniz Imag, F-38031 Grenoble, France
关键词
list-coloring; claw-free graphs;
D O I
10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO;2-B
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 chi denotes the usual chromatic number of G, we are interested in which kind of G is chi-choosable. This question contains a famous conjecture, which states that every line-graph is chi-choosable. We present some other classes of graphs that are chi-choosable; all these classes are related to claw-free graphs. (C) 1998 John Wiley & Sons, Inc.
引用
收藏
页码:87 / 97
页数:11
相关论文
共 12 条
[1]  
Alon N., 1993, LONDON MATH SOC LECT, V187, P1
[2]  
Beineke LW, 1970, J COMB THEORY, V9, P129, DOI 10.1016/S0021-9800(70)80019-9
[3]   RECOGNIZING CLAW-FREE PERFECT GRAPHS [J].
CHVATAL, V ;
SBIHI, N .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (02) :154-176
[4]  
de Werra D., 1985, ASIA PAC J OPER RES, V2, P2
[5]   THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH [J].
GALVIN, F .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :153-158
[6]  
GRAVIER S, 1997, DISC MATH, V166, P353
[7]  
GUTNER S, 1992, THESIS TEL AVIV U
[8]   SOME UPPER-BOUNDS ON THE TOTAL AND LIST CHROMATIC-NUMBERS OF MULTIGRAPHS [J].
HAGGKVIST, R ;
CHETWYND, A .
JOURNAL OF GRAPH THEORY, 1992, 16 (05) :503-516
[9]  
Hall P, 1935, J. Lond. Math. Soc., Vs1-10, P26, DOI [10.1112/jlms/s1-10.37.26, DOI 10.1112/JLMS/S1-10.37.26]
[10]  
Lovasz L., 1986, ANN DISC MATH, V29