论文部分内容阅读
设G=(V,E),图G的一个正常的k-点(边)染色就是k种颜色对点(边)的分配,使得任意相邻的点(边)分配到不同的颜色.一个正常的点染色如果每个色类的大小至多差1,称染色是均匀的.图G的均匀染色数是使得图G是均匀m-可染的最小的整数m,用χeq(G)表示.一个放松的k-染色是对点的k-染色使得每个点与至多一个邻点染相同的颜色.图G的一个放松均匀k-染色(简记ED-k-染色)是图G的点集的一个放松的k-染色使得任意两个色类的大小至多差1.图G的ED-色数是使得G是ED-m-可染的最小整数m,记为χed(G).图G的ED-染色阈值是使得图G对任意n≥ m都是ED-n-可染的最小整数m,记为χed*(G).本文我们证明最小度至少2且围长至少为8的平面图有χed*(G)≤4.图的强边染色是一种正常边染色.要求任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.用χ’s(G)表示.Faudree等人证明任意最大度为△的平面图有χ’s(G)≤ 4△+4.那么△=4时.χ’s(G)≤ 20.最近,Wang等人证得其强边色数不超过19.本文中我们证明不含带弦5-圈和梯子图L3的平面图是18-强边可染的.并且,对最大度为4的平面图,若它是一个非18-强可染的边数极小图.则它一定不存在至多含三条边的非平凡边割.本论文共分为四章.主要研究了平面图的放松均匀染色问题和强边染色问题.第一章,我们主要介绍了图染色问题的背景及意义,给出了本中用到的基本概念与符号,阐述了放松均匀染色和强边染色问题的研究现状,及本文的主要结果.第二章,我们研究了围长至少为8的平面图的放松均匀染色,证明其对任意m≥4都是ED-m-可染的.第三章,我们研究了最大度为4的平面图18-强边染色,给出了一个充分条件.此外,基于图的k-边割,我们讨论了非18-强边可染的极小图的结构.第四章,我们给出了可进一步研究的问题.