与图的顶点染色数有关的几个问题

张祥波



与图的顶点染色数有关的几个问题

张祥波

（临盘中学，山东 临邑 251507）

设是无向简单图的顶点染色数，证明了：若且，则图不存在第类图，其中：，且；若，则；若，则.

顶点染色数；第类图；最大团；图的厚度

1引言及预备知识

定义[9]11如果图含有的所有最大团存在公共顶点，且公共顶点的个数为，则称此图为第类图．

引理1[7]36若，则图含有的所有最大团必存在公共顶点．

引理2[8]67当时，图含最大团，若不存在奇圈，则；若存在奇圈，则．

引理3[7]36若，则．

引理4[8]67当时，图含有最大团，．

引理5[7]36若，则．

引理6[10]215，；，其中：是完全图．

2主要结果及证明

考虑2种情况：

综上可知，假设不成立，定理得证． 证毕．

这些结果为进一步研究图的顶点染色提供了一些参考．

[1] 谢政，戴丽．组合图论[M]．长沙：国防科技大学出版社，2003

[2] 亢莹利，王应前．平面图3色可染的一个充分条件[J]．中国科学·数学，2013，43（4）：409-421

[3] 彩春丽，谢德政．平面图3-可着色的3个充分条件[J]．河南师范大学学报：自然科学版，2011，39（6）：4-6

[4] 刘配配，王应前．不含4-圈与7-圈的平面图是（2，0，0）-可染的[J]．中国科学·数学，2014，44（11）：1153-1164

[5] 刘广德．双外平面图的点染色[J]．枣庄学院学报，2013，30（5）：63-65

[6] 张祥波．研究四色问题的意义及理论构想[J]．数学理论与应用，2012，32（3）：24-28

[7] 张祥波，魏志芹．关于图的色数与厚度的一些新结果[J]．高师理科学刊，2013，33（5）：35-37

[8] 张祥波．一类特殊图的顶点染色及其猜想的证明[J]．重庆工商大学学报：自然科学版，2015，32（9）：66-70

[9] 张祥波．一类特殊图的顶点染色数[J]．安庆师范学院学报：自然科学版，2015，21（3）：11-13

[10] 卜月华．图论及其应用[M]．南京：东南大学出版社，2002

Several problems related to the vertex coloring number of graphs

ZHANG Xiang-bo

（Linpan Middle School，Linyi 251507，China）

Letto be vertex coloring number of undirected simple graph．Proved that ifand

vertex coloring number；-class graph；maximum clique；thickness of a graph

O157.5

A

10.3969/j.issn.1007-9831.2016.03.005

2015-11-20

张祥波（1978-），男，山东临邑人，中教一级，从事图论研究．E-mail：lpzx2010@126.com.