论文部分内容阅读
本文研究了图的多重列表染色和多重在线列表染色中的若干问题.图G的一个b-重染色是一个映射S,将G的每个顶点v对应到一个含b个整数的集合S(v),使得对任意的两个相邻的顶点u和v,S(u)∩ S(v)=φ.G的一个a-列表配置是一个映射L,给G的每一个顶点v配置一个含a个整数的集合L(v).我们称图G是(a∶b)-可选的是指如果对G的每一个a-列表配置L,存在一个b-重染色S,使得S(v)∈ L(v).Erd(o)s,Rubin,Taylor在1979年刻画了所有(2∶1)-可选的图.Tuza和Voigt证明了对任意正整数m,所有的(2∶1)-可选的图均是(2m∶m)-可选的.但是,对m≥2,刻画所有(2m∶ m)-可选的图是未解决的问题. 本文刻画了所有(4∶2)-可选的3-可选临界图,提出了一个刻画所有(4∶2)-可选图的猜想.在线(a∶b)-可选是(a∶b)-可选的在线形式,本文刻画了所有的在线(2m∶ m)-可选图,我们还确定了K2,4的b-重选择数和奇圈的b-重选择数,证明了Brooks定理的在线列表染色版本,研究了多重列表排序染色和多重在线列表排序染色的概念.