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

如果一个图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图所作特征化的一个简单证明．

完全多部图K1*r,3*(k-2)的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K1*r,3*(k-2)具有M(k)性质,且当r≥2时,m(K1*r,3*(k-2))=k.本文将上述结论推广到每一个k,证明了对任意r∈N+,k≥3,图K1*r,3*(k-2)具有M(k)性质,且当k≥4,r≥(k-2)时,m(K1*r,3*(k-2))=k.此外,得到图K1,3,3,3的m数为4,该图是图K1*r,3*(k-2)中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.