论文部分内容阅读
图的非正常染色是由正常染色推广而来.令G=(V, E)是一个图，k是一个正整数，d1，d2，…，dk是k个非负整数.若存在一个映射φ:V→{1，2，…,k}满足:对任意的i∈{1，2，…，k}，染颜色i的点至多有di个邻点染i，则称图G是非正常可染的，简称(d1，d2,…，dk)-可染的.如果d1=d2=…=dk=d，则称图G是（k，d）*-可染的。如果d1=d2=…=dk=0，则称G是k-可染的或（k，0）*-可染的。 本研究分为四个部分：第一章主要对本文中所涉及到的基本概念和符号作一些说明，同时对非正常染色的研究现状作一个综述。第二章主要研究了不含4-圈，5-圈和9-圈的平面图的非正常染色.1976年，Steinberg提出猜想:每个不含4-圈和5-圈的平面图是3-可染的，即(0，0，0)-可染的.围绕Steinberg猜想，后人展开了相关的研究并取得一系列的成果。对于不含4-圈，i-圈和j-圈(5≤i＜j≤9)三类长度圈的平面图，i=5，j=6;i=5，j=9;i=7，j=8和i=8，j=9四类情形的平面图，3-可染问题尚未解决.本章运用权转移方法证明了不含4-圈，5-圈和9-圈的平面图是(1，0，0)-可染的，从而为3-可染问题的解决作了进一步的准备。第三章主要研究了不含4-圈和8-圈的平面图的非正常染色.对于不含4-圈和i-圈(5≤i≤9)两类长度圈的平面图，Lih和W.Wang等人证明了不含4-圈和i-圈(i∈{5，6，7})是(1，1，1)-可染的.随后，B.Xu等人将i的范围扩大到9.本章对i=8的情形作了进一步研究，证明了不含4-圈和8-圈的平面图是(3，0，0)-可染的。第四章主要研究了不含4-圈和5-圈的平面图的非正常染色.为了进一步解决Steinberg猜想，Chang等人证明了不含4-圈和5-圈的平面图是(2，1，0)-可染的和(4，0，0)-可染的.最近，Y.Wang和L.Xu证明了不含4-圈和5-圈的平面图是(3，0，0)-可染的和(1，1，0)-可染的.在本章节中，我们对不含4-圈和5-圈的平面图的(2，0，0)-可染问题作了探究，证明了不含4-圈和5-圈及相交三角形的平面图是(2，0，0)-可染的。