1-平面图的非正常染色的研究

发布时间：2018-04-23 17:37

  本文选题：非正常染色 + 1-平面图　； 参考：《山东师范大学》2017年硕士论文

【摘要】：本文仅考虑有限,简单的无向图.设d1,…,dk是k个非负整数.图G = (V,E)称为是非正常(d1,…,dk)-可染的,或(d1,…,dk)-可染的,当且仅当G的点集可以被剖分成V1,…,Vk,使得每个V1的点导出子图G[Vi]中点的最大度至多为di,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)-可染的.
[Abstract]:In this paper, only finite, simple undirected graphs are considered. Set up D1,... D k is k nonnegative integers. Fig. G = Vt. E) is called abnormal D 1,... DKG-dyed, or D1,... If and only if the set of points of G can be subdivided into V1,... Such that the maximum degree of the midpoint of every vertex derived subgraph G [Vi] of each V1 is more than 1 鈮，

本文编号：1792943