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
    Enomoto, H
    Ohba, K
    Ota, K
    Sakamoto, J
    [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
    Kierstead, HA
    [J]. 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