與圖的頂點染色數有關的幾個問題

張祥波

?

與圖的頂點染色數有關的幾個問題

張祥波

（臨盤中學，山東 臨邑 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.