不含3K1和K1+C4為導(dǎo)出子圖的圖色數(shù)上界?

王 曉

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

1 引言

如果對(duì)于G的任一導(dǎo)出子圖H都有色數(shù)?χ（H）和團(tuán)數(shù) ω（H），則稱(chēng)圖 G 稱(chēng)為完美圖［1］。對(duì)于給定圖H，如果圖G不含與H同構(gòu)的圖為導(dǎo)出子圖，則稱(chēng)圖G是 H-free的（不含 H為導(dǎo)出子圖）。Gyárfás［2］在此基礎(chǔ)上，提出了用 f（ω）表示圖的色數(shù)上界的概念，并給出猜想：設(shè)F是一個(gè)森林，對(duì)于每一個(gè)F-free的圖G，都存在整數(shù)函數(shù)f（x，y）使得 χ（G）≤f（F，ω（G））。關(guān)于此猜想的一些特殊情形的結(jié)論可參閱文獻(xiàn)［3～12］。

設(shè)G1和G2為兩個(gè)圖，它們的聯(lián)圖，記為G1+G2，表 示 滿(mǎn) 足 V（G1+G2）=V（G1）∪V（G2）和E（G1+G2）=E（G1）∪ E（G2）∪{xy|x ∈ V（G1），y∈ V （G2）}的圖。設(shè)3K1表示三個(gè)獨(dú)立點(diǎn)，在文獻(xiàn)［13］中Choudum等給出圖的結(jié)果。

定理1［13］如果G 是一個(gè)不含3K1和 K1+C4為導(dǎo)出子圖的圖，則有 χ（G）≤2ω（G）。

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

本文中所涉及的圖均為無(wú)向、有限、簡(jiǎn)單圖。圖G的頂點(diǎn)集和邊集分別用V（G）和 E（G）來(lái)表示。設(shè) v∈V（G），A?V（G），我們用 NG（v）表示圖G中v的鄰點(diǎn)集，G[A]表示圖G中由頂點(diǎn)子集A導(dǎo)出的子圖。如果G[A]為完全圖，則稱(chēng)A為G的一個(gè)團(tuán)。圖G中最大團(tuán)的階數(shù)稱(chēng)為圖G的團(tuán)數(shù)，記為 ω（G）。如果存在映射 f:?V（G）→{1，2，…，k}使得對(duì)任意的 xy∈E（G）都有 f（x）≠f（y），則稱(chēng)圖G是k-可著色，最小的正整數(shù)k稱(chēng)為圖G的色數(shù)，用 χ（G）來(lái)表示。其他文中涉及到的術(shù)語(yǔ)和符號(hào)可參考文獻(xiàn)［1］。

設(shè) Δ（G）=max{d（v）|v∈V（G）} ，即為圖 G 最大度。顯然有 ω（G）≤χ（G）≤Δ（G）+1。1941年Brooks［1］給出著名的定理：如果圖G是連通圖并且既不是奇圈也不是完全圖，則有 χ（G）≤Δ（G）。1998 年Reed［14］猜想用 ω（G）和 Δ（G）+1的均值作為圖 G 色數(shù)的上界。

猜想1［14］對(duì)每一個(gè)圖G ，都有χ（G）≤

定理2［15］設(shè)圖是滿(mǎn)足 α（G）=2 的圖。如果的補(bǔ)圖的匹配數(shù)滿(mǎn)足，則有否則，有

命題1設(shè)G是不含3K1和K1+C4為導(dǎo)出子圖 的 圖 且 不 同 構(gòu) 于 C5，則 有 ?χ（G）≤

證明如果圖G是不連通的，我只需要對(duì)每個(gè)連通分支分別考慮即可，因此這里我們假設(shè)G是一個(gè)連通圖，下面根據(jù)G的頂點(diǎn)個(gè)數(shù)來(lái)分類(lèi)證明。

情形1|V（G）|≤4。

此時(shí)，?χ（G）=4 當(dāng)且僅當(dāng) ?G=K4；?χ（G）=3 當(dāng)且僅當(dāng) ?G≠K4且 ?G 中含 K3為子圖；?χ（G）=2 當(dāng)且僅當(dāng) ?G 為二部圖。所以成立。

情形2|V（G）|=5。

此時(shí)，?χ（G）=5 當(dāng)且僅當(dāng) ?G=K5。如果 χ（G）≤2 或 χ（G）=5，則顯然有如果 ?χ（G）=4 ，即圖 G 既不是 C5也不是 K5，由Brooks定理，Δ（G）≥χ（G）=4 ，且 G 中必然含有 K3（因?yàn)镚既不是二部圖也不是C5），所以成立。如果 χ（G）=3 ，由ω（G）≥2 ，Δ（G）≥2 ，不成立時(shí)當(dāng)且僅當(dāng) ?ω（G）=Δ（G）=2 ，此時(shí)有G=C5。

情形3|V（G）|≥6。

因?yàn)閳DG不含3K1為導(dǎo)出子圖，所以α（G）≤2 。如果 α（G）=1，則圖 G 是完全圖，即有如 果 α（G）=2 ，又 由（否則，圖 G 含有 K1+C4為其導(dǎo)出子圖），根據(jù)定理 2，所以即 有

3 主要結(jié)論及證明

定理3設(shè)G是不含3K1和K1+C4為導(dǎo)出子圖的圖，則有

1）當(dāng) Δ（G）=|V（G）|-1 或 者 ?G=C5時(shí) ，有

2） 當(dāng) Δ（G）＜|V（G）|-1 且 ?G≠C5時(shí) ，有

證明假設(shè)圖G是階數(shù)最小的不含3K1和K1+C4為導(dǎo)出子圖且滿(mǎn)足的圖。首先G是連通的，否則必有G的一個(gè)連通分支G'滿(mǎn)足不含3K1和K1+C4為導(dǎo)出子圖且滿(mǎn)足這與 G 的階數(shù)最小性矛盾。設(shè)v∈V（G）是 圖 G 中 一 個(gè) 最 大 度 的 點(diǎn) ，即d（v）=Δ（G）。

如果 Δ（G）=|V（G）|-1，則有 ω（G-v）=ω（G）-1。根據(jù) G 的階數(shù)最小性，有所以

如果 ?G=C5，則有

因此，現(xiàn)設(shè) Δ（G）＜|V（G）|-1且 ?G≠C5，則存在w∈V（G）{v}使得 vw?E（G）。令

A={x∈ V（G）|vx∈ E（G），wx∈ E（G）}，

B={x∈ V（G）|vx∈ E（G），wx? E（G）}，

C={x∈ V（G）|vx? E（G），wx∈ E（G）}。

由于圖G不含3K1為導(dǎo)出子圖，因此V（G）=A∪B∪C 且 G[B]和 G[C]都是完全圖。設(shè)A1為G[A]中最大的團(tuán)，令 A2=AA1，則有

結(jié)論1A2=或者G[A2]為完全圖且{xy∈

假設(shè) A2≠，即存在 y1∈A2。若有 x1∈A1使得 x1y1∈E（G），由 A1為 G[A]中最大的團(tuán)，故存在x2∈A1{x1}使得 x2y1?E（G）。這樣則有 G[{v，w，，矛盾。因此有 {xy∈E（G）|x∈現(xiàn) 設(shè) 存 在且 滿(mǎn) 足y1y2?E（G），由 于 x1y1?E（G），x1y2? E（G），即矛盾。所以 G[A2]為完全圖。即結(jié)論1成立。

設(shè)B1={z∈B|存在 y∈A2使得 zy?E（G）}，B2={z∈ B|存在 x∈ A1使得 zx? E（G）}，B3=B（B1∪ B2）。則有

結(jié)論2如果 A2≠，則有G[B1∪A1∪B3]和G[B2∪A2∪B3]都為完全圖。

如果 A2=，因?yàn)镚[A]，?G[B]都是完全圖且 A和B中的點(diǎn)都是v的鄰點(diǎn)，所以有|A|≤ω（G）-1和|B|≤ ω（G）-1 。即有 Δ（G）=d（v）=|A|+|B|≤2ω（G）-2 。 由 ?G≠C5，根 據(jù) 命 題 1，有 χ（G）≤

注 ：當(dāng) ?G ∈{C5，?K1+C5，?K1+（K1+C5）} 時(shí) ，有因 此 ，當(dāng)K1+（K1+C5）}且 G 不含 3K1和 K1+C4為導(dǎo)出子圖時(shí)，但 ?G=K1+（K1+（K1+C5））時(shí) ，有是有可能成立的。

4 結(jié)語(yǔ)

通過(guò)本文的研究，得到了不含3K1和K1+C4為導(dǎo)出子圖的圖的色數(shù)上界，改進(jìn)了Choudum等的結(jié)果，豐富了著色理論的內(nèi)容。