On Uniquely 4-List Colorable Complete Multipartite Graphs

被引：0

作者：

Wang, Yanning ^{[2
,3
]}

Shen, Yufa ^{[1
]}

Zheng, Guoping ^{[1
]}

He, Wenjie ^{[4
]}

机构：

[1] Hebei Normal Univ Sci & Technol, Dept Math & Phys, Qinhuangdao 066004, Peoples R China

[2] Yanshan Univ, Coll Sci, Qinhuangdao 066004, Peoples R China

[3] Yanshan Univ, Inst Elect Engn, Key Lab Ind Comp Control Engn Hebei Prov, Qinhuangdao 066004, Hebei, Peoples R China

[4] Hebei Univ Technol, Inst Appl Math, Tianjin 300401, Peoples R China

来源：

ARS COMBINATORIA | 2009年 / 93卷

基金：

中国国家自然科学基金;

关键词：

List coloring; U4LC graphs; property M(4); complete multipartite graphs;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is called uniquely k-list colorable, or UkLC for short, if it admits a k-list assignment L such that G has a unique L-coloring. A graph C is said to have the property M(k) (M for Marshal Hall) if and only if it is not UkLC. The m-number of a graph G, denoted by m(G), is defined to be the least integer k such that G has the property M(k). After M. Mahdian and E.S. Mohmoodian characterized the U2LC graphs, M. Ghebled and E.S. Mohmoodian characterized the U3LC graphs for complete multipartite graphs except for nine graphs in 2001. Recently, W. He et al. verified all the nine graphs are not U3LC graphs. Namely, the U3LC complete multipartite graphs are completely characterized. In this paper, complete multipartite graphs whose m-number are equal to 4 are researched and the U4LC complete multipartite graphs, which have at least 6 parts, are characterized except for finitely many of them. At the same time, we give some results about some complete multipartite graphs whose number of parts is smaller than 6.

引用

页码：203 / 214

页数：12

共 15 条

[1]

Bollobas B., 2001, Modern Graph Theory

[2]

Dinitz J.H., 1995, Australas. J. Combin., V11, P105

[3]

Erdos P., 1979, C NUMERANTUM, V26, P125

[4]

Eslahchi C., 2002, Journal of Combinatorial Mathematics and Combinatorial Computing, V41, P151

[5]

Ghebleh M, 2001, ARS COMBINATORIA, V59, P307

[6]

HE W, 2003, AUSTRALASIA IN PRESS

[7]

HE W, 2008, K2 2 R R 4 5 6 UNPUB

[8]

KEEDWEEL AD, 1996, CONDR NUMER, P113

[9]

Mahdian M, 1999, ARS COMBINATORIA, V51, P295

[10] Defining sets in vertex colorings of graphs and Latin rectangles [J].

Mahmoodian, ES ;

Naserasr, R ;

Zaker, M .

DISCRETE MATHEMATICS, 1997, 167 :451-460

← 1 2 →