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

作者：王艳宁; 张胜丹; 王妍妍

来源：数学的实践与认识, 2020, 50(10): 296-302.

• 唯一列表染色
• M(k)性质
• 完全多部图
• m数

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

• 单位
  经济管理学院; 燕山大学