非负特征图的非正常染色

摘要

本文主要研究非负特征图的几类染色问题:非正常染色、线性染色及无圈边染色.
　　 图G的一个(点)染色是从顶点集合V(G)到颜色集合S的一个映射c,其中S中的元素称为颜色,染相同颜色的顶点构成一个色类.如果｜S｜=k,则称c是图G的一个k-染色,通常S={1,2,…,k).如果图G的一个k-染色使得图G的相邻顶点都染不同的颜色,则称这样的染色是正常染色.如果图G存在一个正常k-染色,则图G称为k-可染的.图G的点色数是使得图G存在正常染色的最小颜色数,记为χ(G).显然,图G的点色数总是存在,因为总可以给图G的每个顶点各自不同的颜色,从而得到图G的一个正常｜V(G)｜-染色.
　　 列表染色是顶点染色的一个推广,这种染色对于图的每个点可选用的颜色有一定限制.列表染色最初由Vizing及Erd(o)s,Rubin和Taylor提出.图G的一个点列表分派L是指给图G的每个顶点ν一个颜色集合L(ν).给定图G的一个列表分派L,如果图G存在一个正常染色φ使得每个顶点所染的颜色均选自各自的颜色集合L(ν),则称图G是L-可染的或称φ是图G的一个L-染色.如果对于任意给定的图G的列表分派L且每个顶点的颜色集合｜L(ν)｜=k,图G都存在正常染色,则称图G是k-可列表染色或k-可选色的.
　　 我们要讨论的第一种染色问题称为非正常染色(Impropercoloring).
　　 图G被称为是(k,d)*.可染的,如果能用k种颜色对图G的顶点染色,并且使得每个顶点的邻点中至多只有d个与自己染相同的颜色.显然,图G的(k,0)*-染色即为正常染色.对于给定的列表分派L,图G的(L,d)*-染色是指图G的顶点可以L-染色,并且每个顶点的邻点中至多只有d个与自己染相同的颜色.如果对于任意的列表分派L满足每个点的列表集合｜L(ν)｜均为k,图G都存在一个(L,d)*-染色,则称图G是(k,d)*-可选的.上述的非正常选色的概念由(S)krekovski,Eaton和Hull提出.
　　 在第二章,我们将对可嵌入曲面图的(k,d)*-选色做一些研究.具体的,我们得到如下的结论:
　　 (1)每个不含4-圈和8-圈的平面图是(3,1)*-可选色的.
　　 (2)每个不含4-圈和9-圈的平面图是(3,1)*-可选色的.
　　 (3)每个不含3-圈和4-圈的轮胎图是(3,1)*-可选色的；每个不含3-圈和6-圈的轮胎图是(3,1)*-可选色的；每个不含4-圈和6-圈的轮胎图是(3,1)*-可选色的.
　　 (4)每个不含相邻3-圈和5-圈的轮胎图是(3,2)*-可选色的.
　　 (5)每个不含3-圈的轮胎图是(3,2)*-可选色的.
　　 另外一种我们所关注的染色问题是线性染色(Linearcoloring).
　　 图G的线性染色是一个正常染色满足任何两种色类的导出子图是一些不交路的并.图G的线性染色数是图G存在线性染色的最少颜色数,记为lc(G).
　　 文献[40]中已经证明如下结论:每个平面图G,若存在一个有序对(△,9)∈{(13,7),(7,9),(5,11),(3,13)),使得△(G)≥△且g(G)≥9,则lc(G)=「△(G)/2」+1.
　　 文献[40]还证明了每个平面图G,如果g(G)≥6,则lc(G)≤「△(G)/2」+4；如果g(G)≥5,则lc(G)≤「△(G)/2」+14.
　　 在第三章中,我们将得到平面图的线性染色的一些改进的界.我们证明了如下结论:
　　 (1)如果G是围长至少为8的平面图,则lc(G)≤「△(G)/2」+2.
　　 (2)如果G是围长至少为6的平面图,则lc(G)≤「△(G)/2」+3.
　　 (3)如果G是围长至少为5的平面图,则lc(G)≤「△(G)/2」+10.
　　 第三类我们要讨论的染色问题是图的无圈边染色问题(Acyclicedgecoloring).
　　 图G的一个(边)染色是从边集合E(G)到颜色集合S的一个映射c,其中S中的元素称为颜色,染相同颜色的边构成一个色类.如果｜S｜=k,则称c是图G的一个k-边染色.如果图G的一个k-边染色使得图G的相邻的边都染不同的颜色,则称这样的边染色是正常边染色.如果图G存在一个正常k-边染色,则图G称为k-边可染的.图G的边色数是使得图G存在正常边染色的最小颜色数,记为χ’(G).显然,图G的边色数总是存在,因为总可以给图G的每条边各自不同的颜色,从而得到图G的一个正常｜E(G)｜-边染色.
　　 图G的无圈边染色是图G的一个正常边染色满足在这种边染色下不出现双色圈.图G的无圈边色数是使得图G存在无圈边染色的最小颜色数,记为α’(G).
　　 在第四章,我们证明了如下结论:
　　 (1)每个平面图G,若存在一个有序对(△,g)∈.{(8,7),(6,8),(5,9),(4,10),(3,14)},使得△(G)≥△且g(G)≥g,则α’(G)=△(G).
　　 (2)每个平面图G,如果g(G)≥4,则α’(G)≤△(G)+5.
　　 文章的最后,我们提出了一些可进一步研究的问题.