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

王 曉

（商洛學院數(shù)學與計算機應用學院 商洛 726000）

1 引言

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

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

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

2 預備知識

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

設 Δ（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］對每一個圖G ，都有χ（G）≤

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

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

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

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

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

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

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

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

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

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

定理3設G是不含3K1和K1+C4為導出子圖的圖，則有

1）當 Δ（G）=|V（G）|-1 或 者 ?G=C5時 ，有

2） 當 Δ（G）＜|V（G）|-1 且 ?G≠C5時 ，有

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

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

如果 ?G=C5，則有

因此，現(xiàn)設 Δ（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為導出子圖，因此V（G）=A∪B∪C 且 G[B]和 G[C]都是完全圖。設A1為G[A]中最大的團，令 A2=AA1，則有

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

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

設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=，因為G[A]，?G[B]都是完全圖且 A和B中的點都是v的鄰點，所以有|A|≤ω（G）-1和|B|≤ ω（G）-1 。即有 Δ（G）=d（v）=|A|+|B|≤2ω（G）-2 。 由 ?G≠C5，根 據(jù) 命 題 1，有 χ（G）≤

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

4 結(jié)語

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