论文部分内容阅读
本文仅考虑有限,简单的无向图. 设 d1…,d k是 k个非负整数.图 G=(V,E)称为是非正常(d1???,dk)-可染的,或(d1…,dk)-可染的,当且仅当G的点集可以被剖分成V1,…,Vk,使得每个 M的点导出子图G[V]中点的最大度至多为d1,1< i< k.当 d1=…= dk=0时,即为正常k-染色. 一个图 G称为是1-平面图的,如果它可以被画在平面上使得每条边至多交叉另外一条边.1-平面图的概念由Ringel提出,并猜想每个1-平面图都是6-可染的,这已被Borodin(1986)证明.因为存在一个7-正则的1-平面图,所以界6是紧的.在2005年,任意的一个1-平面图是否是(0,0,0,0)-可染的被证明是NP-完备的. 作为图的正常点染色的一种推广,非正常点染色问题已经被广泛研究.1976年,Steinberg提出猜想:每个不含4-圈和5-圈的平面图是(0,0,0)-可染的.在这一猜想的推动下,得到了许多著名结果,例如,每个不含4-圈和5-圈的平面图是(2,1,0)-和(4,0,0)-可染的等. 本文将平面图的非正常染色推广到1-平面图中,在平面图的非正常染色问题的启发下,我们主要讨论不含长度为3,4,5和6的圈的1-平面图,即围长至少是7的1-平面图的非正常点染色问题.第一章介绍了本论文所涉及的有关定义,并对平面图的非正常染色和1-平面图的染色的研究现状做了综述.在第二章和第三章中,我们假设1-平面图 G已经被嵌入到一个平面上使得它的每条边至多交叉另外一条边,通过将G中边的交叉转化成新的4-点,得到其关联平面图G*,并且称G*中新的4-点为交叉点.根据1-平面图 G及其关联平面图G*的结构性质,我们利用权转移的方法分别证明了围长至少是7的1-平面图是(1,1,1,0)-和(2,0,0,0)-可染的.