图的多重列表染色和多重在线列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:zxy6651
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究了图的多重列表染色和多重在线列表染色中的若干问题.图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定理的在线列表染色版本,研究了多重列表排序染色和多重在线列表排序染色的概念.
其他文献
期刊
本文主要评论二阶矩阵特征值问题:4x=M4,借助Bargmann和C.Nemann约束条件建立位势函数(q,r)与特征函数4之间的联系,将其相应发展方程族的Lax对非线性化,得到了特征值问题的Bargman
建筑工程质量已成为人们关注的焦点.影响工程质量的因素是多方面的,要从建设、勘察、设计、施工、监理、监督等单位综合治理,采取措施,按照《建筑法》的要求,严格管理,严格执
期刊
随着集值优化问题(简称SVOP)在经济学、最优控制等领域的发展,集值优化问题的近似解越来越受到国内外学者的重视.本文主要讨论了集值优化问题的近似解的性质和存在性定理,以及
学位
本文主要利用线性矩阵不等式技术和Lyapunov稳定性理论分别研究了连续和离散状态下线性与非线性时滞广义系统的状态反馈H控制问题. 第一部分,研究了线性时滞广义系统的状态
地产开发企业的工程档案除具有一般工程档案共性外,还有其自身的特点,充分认识和掌握这些特点及其管理要求,对加强房地产开发企业工程档案管理并充分发挥其作用,具有十分重要的意
期刊
概率论是有着广不泛应用的一门学科,是许多应用学科的理论基础,诸如信息论,风险数学论;保险精算理论等均是建立在概率论基础上的,强极限定理一直是概率研究的中心问题之一。 本
有效的控制工程造价,可以大量节省工程建设资金,利用有限的资金,获取最大的经济效益和社会效益,从工程项目评估、决策阶段、设计阶段、施工阶段、竣工结算阶段几方面,阐述如
期刊
“十二五”我国煤炭消费比重将从目前的70%以上下降到63%,能源消费结构将逐渐改变。与此同时,在区域内整合完成后,跨区域整合将成为一个重点。“十二五”期间,由于清洁能源和