θr,s,t^＊-图与唯一2-列表染色图的特征化  

θ_(r,s,t)-Graphs and Characterization of Uniquely 2-list Colorable Graphs

作　　者：申玉发 何文杰[2] 赵永强[1] 郑国萍[3] 

机构地区：[1]河北师范大学数学系,石家庄050016 [2]河北工业大学应用数学研究所,天津300130 [3]河北科技师范学院数理系,秦皇岛066004

出　　处：《应用数学与计算数学学报》2005年第2期73-78,共6页Communication on Applied Mathematics and Computation

摘　　要：如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．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 uniquely L-coloring. We say that G has the property M（k） if and only if it is not UkLC. In this paper, we introduce the definition of θr,s,t^＊-graph and show that all θr,s,t^＊-graphs are U2LC except for r = s = t = 2. By the result above we provide a simplified proof of the characterization of U2LC graphs which was given by M. Mahdian and E. S. Mahmoodian.

关 键 词：列表染色 唯一2-列表可染色图 M(2)性质 θr s t^＊-图 特征化 

分 类 号：O157.5[理学—数学] TU05[理学—基础数学]