LIST COLORING OF COMPLETE MULTIPARTITE GRAPHS

被引：2

作者：

Vetrik, Tomas ^{[1
]}

机构：

[1] Univ KwaZulu Natal, Sch Math Sci, Durban, South Africa

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2012年 / 32卷 / 01期

关键词：

list coloring; choice number; complete multipartite graph;

D O I：

10.7151/dmgt.1583

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r - 1 partite classes of order two.

引用

页码：31 / 37

页数：7

共 10 条

[1]

Alon N., 1992, PROBABILITY COMPUTIN, V1, P107

[2]

[Anonymous], P W COAST C COMB GRA

[3] Choice number of some complete multi-partite graphs [J].

Enomoto, H ;

Ohba, K ;

Ota, K ;

Sakamoto, J .

DISCRETE MATHEMATICS, 2002, 244 (1-3) :55-66

[4]

Gravier S, 1998, J GRAPH THEOR, V27, P87, DOI 10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO

[5]

2-B

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

Kierstead, HA .

DISCRETE MATHEMATICS, 2000, 211 (1-3) :255-259

[7]

Tuza Z., 1997, Discussiones Mathematicae Graph Theory, V17, P161

[8]

Vizing V.G., 1976, Diskret. Analiz, P3

[9]

WOODALL DR, 2001, LONDON MATH SOC LECT, V288, P269, DOI DOI 10.1017/CBO9780511721328.012

[10]

YANG D, 2003, THESIS ARIZONA STATE

← 1 →