论文部分内容阅读
本文所考虑的图是有限的,简单的和无向的.令G =(V,E)是一个平面图,k为一个正整数.如果存在一个映射ψ:V → {1,2,...,k}满足使得对任意xy∈E,都有ψ(x)≠ψ(y).则称ψ是G的一个k-染色.若G有一个k-染色,则称G是k-可染的.设d1,d2,...,dk个非负整数,G =(V,E)是分别以V及E为顶点集和边集的图.图G的一个(d1,d2,..…,dk)-染色是一个映射ψ:V → {1,2,…,k}使得子图G[Vi]的最大度至多为di,其中Vi = {v|ψ(∈ = i}.若G存在一个(d1,d2,.....dk)-染色,则称G是(d1,d2,...,dk)-可染的.若d1=d2=…=dk =d,则称G是d-非正常k-可染的,或(k,d)*-可染的.显然G是正常k-可染的等价于它是(0,0,…,0)-可染的;若G是(d1,d2,…,dk)-可染的,则它一定是(d1’,d2’,...,d’k)-可染的,其中di≤di’,i=1,2,...,k.Steinberg在1976年提出了一个著名的猜想:不含4-和5-圈的可平面图是3-可染的.围绕Steinberg猜想,人们提出著名的Bordeaux猜想:既不含5-圈又不含相交三角形的平面图是(3,0)*-可染的(弱的)及既不含5-圈又不含相邻三角形的平面图是(3,0)*-可染的(强的)和Nsk’ s猜想:3-圈不与3-圈和5-圈相邻的平面图是(3,0)*-可染的.围绕着以上几个著名的猜想,后人展开了一系列相关的研究并取得了一些成果.本论文分为三章,主要围绕以上的猜想及相关问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及到的相关定义与符号,并做了一个关于正常和非正常染色的研究现状的综述.第二章介绍了4-圈不与3-,4-圈相邻且不含7-圈的平面图是(1,1,0)-可染的和5--圈不邻的可平面图是(1,1,0)-可染的.第三章介绍了 3-圈不与3-,5-圈相邻的可平面图是(3,1)*-可染的.