论文部分内容阅读
论文中所考虑的图形只是简单,有限,无向图.令G=(V,E)是一个以V为顶点集,E为边集的图,并且k是一个非负整数.如果存在这样的一个映射φ:V→{1,2,…,k},使得对任意uv∈E,都有φ(u)≠φ(v),那么G就有一个k-染色φ,称G是一个k-可染的图. 令d1,d2,…,dk都是非负整数,并且G=(V,E)是一个可平面图.图G的一个(d1,d2,…,dk)-染色是指存在一个映射φ:V→{1,2,…,k},使得诱导子图G[Vi]的最大度至多为di,Vi={v∈V|φ(vi)=i}.如果G有一个(d1,d2,…,dk)-染色,那么称G是(d1,d2,…,dk)-可染的.如果d1=d2=…=dk=d,那么称G是d-非正常k-可染的,或是(k,d)*-可染的. 留意到G是正常k-可染的与G是(0,0,…,0)-可染的是等价的;对于di≥di,i={1,2,…,k},如果G是(d1,d2,…,dk)-可染的,那么它同时是(d1,d2,…,dk)-可染的. Steinberg于1976年提出了一个著名的猜想:不含4-圈和5-圈的可平面图是3-可染的.直至2016年4月,Steinberg的猜想才被证明是错误的.在近四十多年的探索研究过程中,因Steinberg猜想有较大的难度,Erd(o)s认为可先放宽条件研究问题:能否可以找到一个正整数C(≥4l),使得不含4-圈到C-圈的平面图是3-可染的呢?围绕这一问题,众多专家,学者开展一系列相关研究,并取得了丰硕的成果. 本文一共分为三章内容,主要围绕上述的猜想及相关问题开展研究.第一章介绍了本文所涉及到的相关定义与符号,并阐述了关于(d1,d2,d3)-染色的研究现状.第二章介绍了关于(1,1,0)-染色的两个结果.第三章介绍关于(2,0,0)-染色的两个结果.