一类特殊图的顶点染色及其猜想的证明

张祥波(临盘中学，山东临邑251507)

一类特殊图的顶点染色及其猜想的证明

张祥波
(临盘中学，山东临邑251507)

通过研究一类特殊图的顶点染色，得到了以下结果:给出了且p∈{4，5，6}，图G的顶点染色数;证明了的图G不存在第p－m类图，m≥7且m是正整数;证明了时，χ(G)≤4θ(G)+θ2(G)－1;进一步证明了猜想χ(G)≤4θ(G)+θ2(G)－1是正确的;为今后研究该猜想和图的顶点染色提供一些思想方法.

顶点染色;最大团;第k类图;图的厚度

1　基础知识

文中有关的概念和符号参见文献［1，2］.V(G)，E(G)，θ(G)，χ(G)分别是图G的顶点集、边集、厚度、顶点染色数.设S是图G的一个团，由于图G必有最大团，用表示图G最大团的顶点数.如果图G含有的所有最大团存在公共顶点，且公共顶点的个数为k，则称此图为第k类图［1］.图G含有的所有最大团的公共顶点及它们在图G中的边构成的子图，记作图Gs(V'，E')，简称图Gs.V'(Gs)是图G含有的所有最大团的公共顶点集.G－V'表示从G中删去V'(Gs)的所有顶点及其与V'(Gs)中顶点关联的一切边后得到的图.

一般图的顶点染色是非常复杂的，目前较多地是研究特殊图的顶点染色［3－7］.为研究一般图的顶点染色，文献［8］提出了图的色数与厚度的猜想:χ(G)≤4θ(G)+θ2(G)－1.文献［9］定理3—5分别证明了完全图、时，猜想是成立的;文末提出了有待研究的2个问题:

问题1［9］时，χ(G)≤4θ(G)+θ2(G)－1是否成立?

问题2［9］若则χ(G)=p－3或p－2，那么满足什么条件的图，χ(G)=p－3;满足什么条件的图，χ(G)=p－2.

文献［1］通过研究问题2，提出了研究图的顶点染色的一种新方法，并利用该方法得到了该问题在时，图的4种顶点染色.

引理1［1］的图G，若图Gs中存在一个顶点与图G－V'的顶点中至少一个不相邻，则χ(G)=p－3.

引理2［1］的图G，若只含有一个最大团Kp－3，则χ(G)=p－3.

引理3［1］如果的图G满足下列条件:

1)V'(Gs)中任意一个顶点与V(G－V')中的所有顶点相邻;

2)图G是第p－4类图或第p－6类图.

则χ(G)=p－3.

引理4［1］图G满足下列条件:

1)V'(Gs)中任意一个顶点与V(G－V')中的所有顶点相邻;

2)图G是第p－5类图.

若图G－V'中不存在奇圈，则χ(G)=p－3;若图G－V'中存在奇圈，则χ(G)=p－2.

但问题2尚未完全解决，文献［1］在文末将其未解决的部分总结为第5个问题.此处的研究是给出p－3且p∈{4，5，6}，图的各种顶点染色;证明时，图G不存在第p－m类图，m≥7且m是正整数.进一步证明文献［9］提出的问题1是成立的.综合上述4个引理，从而完全解决文献［9］提出的第2个问题.

①p=4时，S=1，则χ(G)=1;

②p=5时，图G含最大团K2，若不存在奇圈，则χ(G)=2;若存在奇圈，则χ(G)=3.

证明图G若存在奇圈，由于含最大团K2，所以奇圈必是5－圈，于是χ(G)=3.

其次考虑图G不存在奇圈的情况，若所有最大团K2有公共顶点，则只有一个公共顶点，于是必有χ(G)=2;若所有最大团K2不存在公共顶点，由文献［1］定理4的证明可知χ(G)=2.

引理5［9］若，则χ(G)=p－2.

①若该公共顶点与图G－V'中的一个顶点不相邻，则χ(G)=3;

②若该公共顶点与图G－V'中的所有顶点相邻，且图G－V'存在奇圈，则χ(G)=4;

③若该公共顶点与图G－V'中的所有顶点相邻，且图G－V'不存在奇圈，则χ(G)=3.

证明先证①，设u是图G所有最大团K3的公共顶点，v是图G－V'的一个顶点，u和v不相邻，将u和v删掉，必得到一个顶点数是4，含最大团K2的图G1.由引理5知，χ(G1)=2，添上顶点u和v，则图G的色数增加1，故χ(G)=3.

关于②，设u是所有最大团K3的公共顶点，则G－V'是一个顶点数是5，含最大团K2的图.由于图G－V'存在奇圈，则必是一个5－圈，所以χ(G－V')=3，由于u与图G－V'的所有顶点相邻，故χ(G)=4.

关于③，由条件知，图G－V'是一个顶点数是5，含最大团K2的图.由于图G－V'不存在奇圈，所以由文献［1］定理4的证明可知，χ(G)=3.

证明分两种情况.

情况1有一个公共顶点与图G－V'中的一个顶点不相邻.设u是图G所有最大团K3的公共顶点，v是图G－V'的一个顶点，u和v不相邻，将u和v删掉，必得到一个顶点数是4，含最大团K2的图G1.由引理5知，χ (G1)=2，添上顶点u和v，则图G的色数增加1，故χ(G)=3.

情况2 2个公共顶点与图G－V'的所有顶点相邻，则图G－V'中所有顶点互不相邻，于是χ(G－V')=1，故χ(G)=3.

由文献［1］定理3的证明可知该定理成立，此处证明略.

3　关于第p－m类图

引理6［9］若，则图G含有的所有最大团必存在公共顶点.

证明使用反证法证明.

假设图G是第p－m类图，则图G中所有最大团Kp－3有p－m个公共顶点.考虑其中一个最大团S1，则必有3个顶点不是S1的顶点.不妨设这3个顶点分别是u1，u2，u3，于是u1，u2，u3中至少有一个顶点在除S1外的最大团Kp－3中.考虑3种情况:

情况1若u1，u2，u3都是最大团Kp－3(除S1外)的顶点，则图Gs与图G－V'所有顶点相邻.于是将图Gs的所有顶点都删去，必得到一个顶点数是m，含有最大团的顶点数是m－3的图G1.由于m≥7，故由引理6知，图G1中所有最大团Km－3必有公共顶点.从而图G中所有最大团Kp－3的公共顶点数大于p－m，这与图G中所有最大团Kp－3有p－m个公共顶点矛盾.

情况2u1，u2，u3中只有一个顶点是最大团Kp－3的顶点.不妨设u1是最大团Kp－3的顶点，则u2和u3不是最大团Kp－3的顶点.于是将图Gs及u2，u3都删掉，必得到顶点数是m－2，含最大团Km－3的图G'.由于m≥7，故由引理6知，图G'中所有最大团K必有公共顶点.从而图G中所有最大团K的公共顶点数

m－3p－3大于p－m，这与图G中所有最大团Kp－3有p－m个公共顶点矛盾.

情况3u1，u2，u3中只有2个顶点是最大团Kp－3的顶点.不妨设u1和u2是最大团Kp－3的顶点，则u3不是最大团Kp－3的顶点.将图Gs和u3都删掉，必得到一个顶点数是m－1，含最大团Km－3的图G2.由于m≥7，故.由引理6知，图G2中所有最大团Km－3必有公共顶点.从而图G中所有最大团Kp－3的公共顶点数大于p－m，这与图G中所有最大团Kp－3有p－m个公共顶点矛盾.

综合以上3种情况，假设不成立，定理得证.

引理7［9］若，则χ(G)≤p－2.

引理8［10］，其中Kn是完全图.

证明由前面的结论易知，p=4时，χ(G)=1;p=5时，χ(G)=2或3;p=6时，由定理1，定理2，定理3，定理4知，χ(G)=3或4，而4θ(G)+θ2(G)－1≥4.故且p∈{4，5，6}时，χ(G)≤4θ(G)+θ2(G)－1.

②p=6k－1，6k－2，6k－3，6k－4时，同理可证，均有χ(G)≤4θ(G)+θ2(G)－1.

综上各种情况得证，S =p－3时，有χ(G)≤4θ(G)+θ2(G)－1.

5　结束语

在文献［1］的基础上，解决了文献［1］在文末提出的第5个问题，结合文献［1］已经得到的4个定理，从而完全解决了文献［9］提出的问题2.这为研究时，图的顶点染色，提供了一些思想和方法.文末利用这些结论，证明了文献［9］提出的问题1是正确的.因此，有理由猜测时，该猜想是否成立.至此，文献［9］提出的2个问题已全部解决;同时文献［1］提出的5个有待研究的问题中，还有3个尚待研究.另外注意到证明的定理4，由此猜想的图G，是否存在第p－q类图，q≥2m+1，m≥3且m是正整数.此外定理4证明了m=3的情况是不存在的，对于m≥4的情况还有待研究.

［1］张祥波.一类特殊图的顶点染色数［J］.安庆师范学院学报:自然科学版，2015，21(3):130-135

［2］谢政，戴丽.组合图论［M］.长沙:国防科技大学出版社，2003

［3］刘广德，双外平面图的点染色［J］.枣庄学院学报，2013，30(5):63-65

［4］亢莹利，王应前.平面图3色可染的一个充分条件［J］.中国科学:数学，2013，43(4):409-421

［5］彩春丽，谢德政.平面图3－可着色的3个充分条件［J］.河南师范大学学报:自然科学版，2011，39(6):4-6;28

［6］刘配配，王应前.不含4－圈与7－圈的平面图是(2，0，0)－可染的［J］.中国科学:数学，2014，44(11):1153-1164

［7］胡凤凤，刘家保.关于一类图的邻点可区别全染色［J］.重庆工商大学学报:自然科学版，2015，32(2):23-26

［8］张祥波.研究四色问题的意义及理论构想［J］.数学理论与应用，2012，32(3):24-28

［9］张祥波，魏志芹.关于图的色数与厚度的一些新结果［J］.高师理科学刊，2013，33(5):35-37

［10］卜月华.图论及其应用［M］.南京:东南大学出版社，2002

(1)Give vertex coloring number of graph G=p－3and p∈{4，5，6}.

(2)Prove that graph G ofhas no the p－m class of graph，m≥7and m is positive integer.

(3)Prove thatχ(G)≤4θ(G)+θ2(G)－1，when

All kinds of vertex coloring number of graph G whenare given from these results above，and further it is proven that the conjectureχ(G)≤4θ(G)+θ2(G)－1 is right.，which provide some thoughts and methods for further study on this conjecture and the graph vertex coloring.

Proof of a Conjecture of A Class of Vertex Coloring of Special Graphs

ZHANG Xiang-bo
(Linpan Middle School，Linyi 251507，China)

Throughout the study on a class of vertex coloring of special graphs，this paper gives the following results:

vertex coloring，themaximum clique，thekclass of graph，thickness of a graph

O157.5

A

1672－058X(2015)09－0066－05

10.16055/j.issn.1672－058X.2015.0009.017

2015－01－23;

2015－03－11.

张祥波(1978-)，山东临邑人，中教一级，从事图的染色研究.