不含3K1和K1+C4为导出子图的图色数上界∗

王 晓

（商洛学院数学与计算机应用学院 商洛 726000）

1 引言

如果对于G的任一导出子图H都有色数 χ（H）和团数 ω（H），则称图 G 称为完美图［1］。对于给定图H，如果图G不含与H同构的图为导出子图，则称图G是 H-free的（不含 H为导出子图）。Gyárfás［2］在此基础上，提出了用 f（ω）表示图的色数上界的概念，并给出猜想：设F是一个森林，对于每一个F-free的图G，都存在整数函数f（x，y）使得 χ（G）≤f（F，ω（G））。关于此猜想的一些特殊情形的结论可参阅文献［3～12］。

设G1和G2为两个图，它们的联图，记为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等给出图的结果。

定理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中最大团的阶数称为图G的团数，记为 ω（G）。如果存在映射 f: V（G）→{1，2，…，k}使得对任意的 xy∈E（G）都有 f（x）≠f（y），则称图G是k-可着色，最小的正整数k称为图G的色数，用 χ（G）来表示。其他文中涉及到的术语和符号可参考文献［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 色数的上界。

猜想1［14］对每一个图G ，都有χ（G）≤

定理2［15］设图是满足 α（G）=2 的图。如果的补图的匹配数满足，则有否则，有

命题1设G是不含3K1和K1+C4为导出子图 的 图 且 不 同 构 于 C5，则 有  χ（G）≤

证明如果图G是不连通的，我只需要对每个连通分支分别考虑即可，因此这里我们假设G是一个连通图，下面根据G的顶点个数来分类证明。

情形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为其导出子图），根据定理 2，所以即 有

3 主要结论及证明

定理3设G是不含3K1和K1+C4为导出子图的图，则有

1）当 Δ（G）=|V（G）|-1 或 者  G=C5时 ，有

2） 当 Δ（G）＜|V（G）|-1 且  G≠C5时 ，有

证明假设图G是阶数最小的不含3K1和K1+C4为导出子图且满足的图。首先G是连通的，否则必有G的一个连通分支G'满足不含3K1和K1+C4为导出子图且满足这与 G 的阶数最小性矛盾。设v∈V（G）是 图 G 中 一 个 最 大 度 的 点 ，即d（v）=Δ（G）。

如果 Δ（G）=|V（G）|-1，则有 ω（G-v）=ω（G）-1。根据 G 的阶数最小性，有所以

如果  G=C5，则有

因此，现设 Δ（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，则有

结论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∈现 设 存 在且 满 足y1y2∉E（G），由 于 x1y1∉E（G），x1y2∉ E（G），即矛盾。所以 G[A2]为完全图。即结论1成立。

设B1={z∈B|存在 y∈A2使得 zy∉E（G）}，B2={z∈ B|存在 x∈ A1使得 zx∉ E（G）}，B3=B（B1∪ B2）。则有

结论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，根 据 命 题 1，有 χ（G）≤

注 ：当  G ∈{C5， K1+C5， K1+（K1+C5）} 时 ，有因 此 ，当K1+（K1+C5）}且 G 不含 3K1和 K1+C4为导出子图时，但  G=K1+（K1+（K1+C5））时 ，有是有可能成立的。

4 结语

通过本文的研究，得到了不含3K1和K1+C4为导出子图的图的色数上界，改进了Choudum等的结果，丰富了着色理论的内容。