Choice number of some complete multi-partite graphs

被引：23

作者：

Enomoto, H ^{[1
]}

Ohba, K ^{[1
]}

Ota, K ^{[1
]}

Sakamoto, J ^{[1
]}

机构：

[1] Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan

来源：

DISCRETE MATHEMATICS | 2002年 / 244卷 / 1-3期

关键词：

list coloring; complete multi-partite graphs;

D O I：

10.1016/S0012-365X(01)00059-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

One of the authors has conjectured that every graph G with 2chi(G) + 1 or fewer vertices is chi(G)-choosable. Motivated by this, we investigate the choice numbers of some complete k-partite graphs of order slightly larger than 2k, and settle the conjecture for some special cases. We also present several complete multi-partite graphs whose choice numbers are not equal to their chromatic numbers. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：55 / 66

页数：12

共 8 条

[1] Erd o P., 1979, Congr. Numer., V26, P125
[2] THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH
GALVIN, F
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) : 153 - 158
[3] Gravier S, 1998, J GRAPH THEOR, V27, P87, DOI 10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO
[4] 2-B
[5] Choice number of 3-colorable elementary graphs
Gravier, S
Maffray, F
[J]. DISCRETE MATHEMATICS, 1997, 165 : 353 - 358
[6] On the choosability of complete multipartite graphs with part size three
Kierstead, HA
[J]. DISCRETE MATHEMATICS, 2000, 211 (1-3) : 255 - 259
[7] OHBA K, CHROMATIC CHOOSABLE
[8] Vizing V.G., 1976, Diskret. Analiz. no. 29, Metody Diskret. Anal. v Teorii Kodovi Skhem, V29, P3

← 1 →