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

The m-number of Complete Multipartite Graphs K1*r,3*(k-2)

如果对一个图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时的特殊情况,同时也是现有研究中尚未解决的一个问题.

We say that a graph G has the property M(k) if for any collection of lists assigned to its vertices,each of size k,either there is no k-list coloring for G or there are at least two k-list colorings.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).Existing studies show that K1*r,3*(k-2)have the property M(k) when k=3,4,and m(K1*r,3*(k-2)= k when k=3,4 and r≥2.In this paper,it is generalized the above conclusion to every k,and we will show that for every r ∈ N+,k≥ 3,K(1*r,3*(k-2) has the property M(k),and if k≥ 4 and r≥(k-2),m(K1*r,3*(k-2)= k.In addition,it is obtained the m-number of the graph K1,3,3,3 which is a specific case of K(1*r,3*(k-2) when r= 1 and k=5,as is an unsolved problem in previous studies.