论文部分内容阅读
G的点染色是G的顶点集的一个剖分.如果G的顶点集V可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[Vi]满足某种特定要求.若V1,V2,…,Vk是点独立集,则称这种染色是正常染色；若V1,V2,…,Vk不是点独立集,则称这种染色是非正常染色.如果图G可以用k种颜色正常染色,则称G为k可染的.令x(G)=min{k|G是k色可染的},称χ(G)为图G的点色数,有时简称为色数.论文第一章主要介绍了一些基本概念和符号,阐述了图的非正常点染色的历史及发展,本文中未加说明的术语和符号参见文献[1]. 定义1.2.1令G=(V,E)是一个图,图G的一种退化染色是把图G的顶点剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[K]中所有顶点的度数不超过di,则称图G是(d1,d2,…,dk)可染的. 这种非正常染色是对每个色类的点导出子图中顶点的度数做限制.1976年,Steinberg提出了如下猜想. 猜想1.2.1[2]不含4-圈和5-圈的平面图是三色可染的,即(0,0,0)-可染的. 为了证明这一猜想,一些学者将染色推广到了退化染色,主要有以下结果. 定理1.2.3 (1)[14]若图G为平面图,且不含相交三角形和5-圈,则图G是(1,1,0)-可染的. (2)[15]若图G为平面图,且不含相交三角形和5-圈,则图G是(2,0,0)-可染的. (3)[16]若图G为平面图,且不含邻接三角形和5-圈,则图G是(1,1,1)-可染的. (4)[17]若图G为平面图,且不含4-圈和5-圈,则图G是(1,1,0)-可染的. (5)[18]若图G为平面图,且不含4-圈和5-圈,则图G是(3,0,0)-可染的. (6)[19]图G为平面图,且不含4-圈和6-圈,则图G是(1,1,0)-可染的. (7)[20]若图G为平面图,且不含4-圈和6-圈,则图G是(2,0,0)-可染的. 当G[Vi]给定其它限制时,可以导出图G的几类其它染色.例如定义1.2.2定义的这种非正常染色. 定义1.2.2 令G=(V,E)是一个图,如果图G的顶点可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[Vi]为森林,满足上述条件的k的最小值称为图G的点荫度,记作va(G). 孙磊老师在2015年提出了一种新的非正常染色,这种染色规定G[Vi]不含长度超过l(l≥0)的路Pl,这里l指路P的边数,具体定义如下. 定义1.2.3如果图G的顶点可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi= V,Vi∩Vj=0对任意i≠j成立,且Vi的导出子图G[Vi]不含长度超过l(l≥0)的路Bl,其中1≤i≤k,则称图G有一个Pl-染色(称作是Pl-可染的).使得图G有不含长度超过l(l≥0)的路Pl染色的最小剖分数k叫做图G的Pl-染色数,记作xpl(G). 论文第二章主要研究了简单图的P2-染色,尤其是具有低最大度图的P2-染色,分别给出了△(G)≤3及△(G)≤4时,图G的P2-色数的上界,并且证明了这个上界是紧的. 定理2.1.1对任意简单图G,若△(G)≤3,则χρ2(G)≤2. 这个色数上界是紧的,因为任意一条路长超过2的路都必须至少用两个颜色来染. 定理2.1.1’对任意简单图G,若△(G)≤3,可在多项式时间内找到一个图G的色数至多为2的P2—染色. 定理2.2.1对任意简单图G,若△(G)≤4,则χρ2(G)≤3. 定理2.2.1’对任意简单图G,若△(G)≤4,可在多项式时间内找到一个图G的色数至多为3的P2-染色. 这个色数上界是紧的,比如如下定义的图G: V(G)={vij|i=1,2,3;j=1,2,3}; E(G)={vijvi(j+1)|i=1,2,3;j=1,2}∪{vk3vk1|k=1,2,3}. 显然△(G)=4. 定理2.2.2对于上述图G,有xp2(G)=3. 论文第三章主要研究了部分特殊图的P2-染色及Pl—染色. 定理3.1对于n阶完全图G,有xp2(G)=[n/3]. 定义3.1对于任意图G=(V1,E1)和H=(V2,E2),笛卡尔乘积图定义如下: V(G□H)=V1×V2={(vi,vj)|(?)ui∈V1,vj∈V2}; E(G□H)={(u1,v1),(u2,v2)|v1=v2且(u1,u2)∈E1或u1=u2且(u1,u2)∈E2}. 定理3.2对于任意n阶图G及有t个顶点的路Pt-1,若xpl(G)=k且k>2.l≥0,则xpl(Pt-1□G)=k. 定理3.3对于任意n阶图G及有t个顶点的圈Ct,若xpl(G)=k且k≥3,l≥0,则xpl(Ct□G)=k. 当χρl(G)=2时,我们有下述两个结论. 定理3.4对于任意n阶图G及有2m个顶点的圈G2m,若xpl(G)=2,l≥0,则xpl(G2m□G)=2. 定理3.5对于任意n阶图G及有2m1个顶点的圈G2m+1,若xpl(G)=2,l≥0,则xpl(G2m+1□G)≤3.