Choice number of some complete multi-partite graphs

被引：26

作者：

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 [J].

GALVIN, F .

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 [J].

Gravier, S ;

Maffray, F .

DISCRETE MATHEMATICS, 1997, 165 :353-358

[6] On the choosability of complete multipartite graphs with part size three [J].

Kierstead, HA .

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 →