禁用子圖為P3∪mP2的圖色數(shù)上界

王曉

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000）

色數(shù)和團(tuán)數(shù)是圖的兩個(gè)重要參數(shù)，著名圖論專(zhuān)家Erd?s利用概率的方法證明了色數(shù)和團(tuán)數(shù)的差值可以是任意大的整數(shù)[1-2]。顯然，一個(gè)圖的色數(shù)至少等于其團(tuán)數(shù)，這就促使研究者去考慮色數(shù)和團(tuán)數(shù)相等的圖。一個(gè)k-可著色的圖和階數(shù)為k的完全圖的不交并所構(gòu)成圖滿(mǎn)足色數(shù)和團(tuán)數(shù)相等。因此，單純考慮圖本身的色數(shù)和團(tuán)數(shù)相等意義不大。Berge[3]提出了完美圖的概念：不但要求圖本身的色數(shù)和團(tuán)數(shù)相等，同時(shí)要滿(mǎn)足其所有的導(dǎo)出子圖的色數(shù)和團(tuán)數(shù)也相等。與此同時(shí)，Berge提出了兩個(gè)關(guān)于完美圖的猜想（弱完美圖猜想和強(qiáng)完美圖猜想）。弱完美圖猜想是：一個(gè)圖是完美圖當(dāng)且僅當(dāng)其補(bǔ)圖是完美圖，隨后被Lovász[4]證明，稱(chēng)為完美圖定理。強(qiáng)完美圖猜想是：一個(gè)圖是完美圖當(dāng)且僅當(dāng)其本身和其補(bǔ)圖都不含長(zhǎng)度大于等于5的奇長(zhǎng)圈為導(dǎo)出子圖，在2006年被Chudnovsky等[5]證明，稱(chēng)為強(qiáng)完美圖定理?；谕昝缊D的定義，Gyárfás[6]提出了圖的色界函數(shù)的概念，即：什么樣的圖存在以團(tuán)數(shù)為變量的函數(shù)使得其任意導(dǎo)出子圖的色數(shù)都以這個(gè)函數(shù)為上界。 在文獻(xiàn)[6]中，Gyárfás給出了猜想 1。

猜想1[6]設(shè)F是一個(gè)森林，存在整數(shù)函數(shù)f(F,x)使得對(duì)于每一個(gè)以F為禁用子圖的圖G都滿(mǎn)足 χ(G)≤ f(F,ω(G))，其中 χ(G)和 ω(G)分別表示圖G的色數(shù)和團(tuán)數(shù)。

圍繞猜想1，眾多學(xué)者進(jìn)行了廣泛的研究，已有豐富的結(jié)果[7-13]。特別地，Wagon[9]證明了禁用子圖為兩條獨(dú)立邊的圖的一個(gè)色界函數(shù)為Choudum[12]研究了獨(dú)立數(shù)小于等于2的圖色界函數(shù)。因此，禁用子圖為階數(shù)較小的森林是一個(gè)研究的重點(diǎn)。

設(shè)P3∪P2表示路P3和P2的不交并，P3∪mP2表示路P3和m條不交邊 P2的不交并。本文通過(guò)對(duì)以P3∪P2為禁用子圖的圖結(jié)構(gòu)進(jìn)行分析，給出色界函數(shù) f(P3∪P2，ω(G))的一個(gè)上界；并且以此為基礎(chǔ)，得到禁用子圖為P3∪mP2的圖色數(shù)上界。

1 預(yù)備知識(shí)

圖是一個(gè)具有二元關(guān)系結(jié)構(gòu)的數(shù)學(xué)模型，是由頂點(diǎn)集和邊集構(gòu)成的有序?qū)?，通常用G=(V(G),E(G))表示。設(shè)H和G表示兩個(gè)圖，若滿(mǎn)足V(H)?V(G)和 E(H)?E(G)，則稱(chēng) H 是 G 的子圖；更進(jìn)一步，對(duì)于任意 u,v∈V(H)，若uv∈E(H)當(dāng)且僅當(dāng)uv∈E(G)，則稱(chēng)H是G的導(dǎo)出子圖。若圖G不含H為導(dǎo)出子圖，則稱(chēng)H是G的禁用子圖。設(shè)u,v∈V(G)，若uv∈E(G)則稱(chēng)頂點(diǎn)u和v相鄰，且u，v互為鄰點(diǎn)；圖G中v的所有鄰點(diǎn)構(gòu)成的集合稱(chēng)為v的鄰點(diǎn)集，記為NG(v)。

設(shè)G是一個(gè)圖，對(duì)于頂點(diǎn)子集A?V(G)，用G[A]表示圖G中由A導(dǎo)出的子圖。如果E(G[A])=?，則稱(chēng)A為圖G的一個(gè)獨(dú)立集。如果G[A]為完全圖，則稱(chēng)A為圖G的一個(gè)團(tuán)。圖G中最大團(tuán)的階數(shù)稱(chēng)為G的團(tuán)數(shù)，記為ω(G)。對(duì)于圖G，如果存在映射 f:V(G)→{1，2，…，k}使得對(duì)任意的 uv∈E(G)都有f（u）≠f（v），則稱(chēng)G是k-可著色；使得圖G有k-可著色的最小的正整數(shù)k稱(chēng)為G的色數(shù)，用 χ(G)表示。

不重復(fù)的點(diǎn)邊交錯(cuò)序列稱(chēng)為路，n個(gè)頂點(diǎn)的路記為Pn。若圖G中任意兩個(gè)頂點(diǎn)之間都有路相連，則稱(chēng)G為連通圖。圖中與某一頂點(diǎn)相鄰的頂點(diǎn)數(shù)目稱(chēng)為該頂點(diǎn)的度，連通且每個(gè)頂點(diǎn)的度都為2的圖稱(chēng)為圈，不含圈的連通圖稱(chēng)為樹(shù)，森林為某些樹(shù)的不交并。

本文中考慮的圖都是有限簡(jiǎn)單圖，文中涉及到但未給出的概念和記號(hào)可參考文獻(xiàn)[7,14]。

2 禁用子圖為P3∪P2的圖著色

3 禁用子圖為P3∪mP2的圖著色

4 結(jié)語(yǔ)

根據(jù)強(qiáng)完美圖定理可知完美圖的禁用子圖是奇長(zhǎng)圈及其補(bǔ)圖。 1987 年 Gyárfás[6]提出一系列的具有禁用子圖的色界函數(shù)的猜想，并引起圖論學(xué)者的廣泛研究。Wagon[9]早在1980年就給出了禁用子圖為2P2的圖的一個(gè)色界函數(shù)，雖然這個(gè)色界函數(shù)不是緊的，但是四十年來(lái)一直沒(méi)有被改進(jìn)，足以說(shuō)明尋找色界函數(shù)的難度。本文首先借鑒Wagon的方法給出禁用子圖為P3∪P2的圖的色界函數(shù)，進(jìn)而得到了禁用子圖為P3∪mP2的圖類(lèi)的色數(shù)上界，說(shuō)明了Gyárfás猜想（猜想1）在F為特殊森林時(shí)是成立的。