與圖的頂點(diǎn)染色數(shù)有關(guān)的幾個(gè)問題

張祥波

?

與圖的頂點(diǎn)染色數(shù)有關(guān)的幾個(gè)問題

張祥波

（臨盤中學(xué)，山東 臨邑 251507）

設(shè)是無向簡單圖的頂點(diǎn)染色數(shù)，證明了：若且，則圖不存在第類圖，其中：，且；若，則；若，則.

頂點(diǎn)染色數(shù)；第類圖；最大團(tuán)；圖的厚度

1引言及預(yù)備知識

定義[9]11如果圖含有的所有最大團(tuán)存在公共頂點(diǎn)，且公共頂點(diǎn)的個(gè)數(shù)為，則稱此圖為第類圖．

引理1[7]36若，則圖含有的所有最大團(tuán)必存在公共頂點(diǎn)．

引理2[8]67當(dāng)時(shí)，圖含最大團(tuán)，若不存在奇圈，則；若存在奇圈，則．

引理3[7]36若，則．

引理4[8]67當(dāng)時(shí)，圖含有最大團(tuán)，．

引理5[7]36若，則．

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

2主要結(jié)果及證明

考慮2種情況：

綜上可知，假設(shè)不成立，定理得證． 證畢．

這些結(jié)果為進(jìn)一步研究圖的頂點(diǎn)染色提供了一些參考．

[1] 謝政，戴麗．組合圖論[M]．長沙：國防科技大學(xué)出版社，2003

[2] 亢瑩利，王應(yīng)前．平面圖3色可染的一個(gè)充分條件[J]．中國科學(xué)·數(shù)學(xué)，2013，43（4）：409-421

[3] 彩春麗，謝德政．平面圖3-可著色的3個(gè)充分條件[J]．河南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，39（6）：4-6

[4] 劉配配，王應(yīng)前．不含4-圈與7-圈的平面圖是（2，0，0）-可染的[J]．中國科學(xué)·數(shù)學(xué)，2014，44（11）：1153-1164

[5] 劉廣德．雙外平面圖的點(diǎn)染色[J]．棗莊學(xué)院學(xué)報(bào)，2013，30（5）：63-65

[6] 張祥波．研究四色問題的意義及理論構(gòu)想[J]．?dāng)?shù)學(xué)理論與應(yīng)用，2012，32（3）：24-28

[7] 張祥波，魏志芹．關(guān)于圖的色數(shù)與厚度的一些新結(jié)果[J]．高師理科學(xué)刊，2013，33（5）：35-37

[8] 張祥波．一類特殊圖的頂點(diǎn)染色及其猜想的證明[J]．重慶工商大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，32（9）：66-70

[9] 張祥波．一類特殊圖的頂點(diǎn)染色數(shù)[J]．安慶師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2015，21（3）：11-13

[10] 卜月華．圖論及其應(yīng)用[M]．南京：東南大學(xué)出版社，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.