禁用子图为P3∪mP2的图色数上界

王晓

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

色数和团数是图的两个重要参数，著名图论专家Erdös利用概率的方法证明了色数和团数的差值可以是任意大的整数[1-2]。显然，一个图的色数至少等于其团数，这就促使研究者去考虑色数和团数相等的图。一个k-可着色的图和阶数为k的完全图的不交并所构成图满足色数和团数相等。因此，单纯考虑图本身的色数和团数相等意义不大。Berge[3]提出了完美图的概念：不但要求图本身的色数和团数相等，同时要满足其所有的导出子图的色数和团数也相等。与此同时，Berge提出了两个关于完美图的猜想（弱完美图猜想和强完美图猜想）。弱完美图猜想是：一个图是完美图当且仅当其补图是完美图，随后被Lovász[4]证明，称为完美图定理。强完美图猜想是：一个图是完美图当且仅当其本身和其补图都不含长度大于等于5的奇长圈为导出子图，在2006年被Chudnovsky等[5]证明，称为强完美图定理。基于完美图的定义，Gyárfás[6]提出了图的色界函数的概念，即：什么样的图存在以团数为变量的函数使得其任意导出子图的色数都以这个函数为上界。 在文献[6]中，Gyárfás给出了猜想 1。

猜想1[6]设F是一个森林，存在整数函数f(F,x)使得对于每一个以F为禁用子图的图G都满足 χ(G)≤ f(F,ω(G))，其中 χ(G)和 ω(G)分别表示图G的色数和团数。

围绕猜想1，众多学者进行了广泛的研究，已有丰富的结果[7-13]。特别地，Wagon[9]证明了禁用子图为两条独立边的图的一个色界函数为Choudum[12]研究了独立数小于等于2的图色界函数。因此，禁用子图为阶数较小的森林是一个研究的重点。

设P3∪P2表示路P3和P2的不交并，P3∪mP2表示路P3和m条不交边 P2的不交并。本文通过对以P3∪P2为禁用子图的图结构进行分析，给出色界函数 f(P3∪P2，ω(G))的一个上界；并且以此为基础，得到禁用子图为P3∪mP2的图色数上界。

1 预备知识

图是一个具有二元关系结构的数学模型，是由顶点集和边集构成的有序对，通常用G=(V(G),E(G))表示。设H和G表示两个图，若满足V(H)⊆V(G)和 E(H)⊆E(G)，则称 H 是 G 的子图；更进一步，对于任意 u,v∈V(H)，若uv∈E(H)当且仅当uv∈E(G)，则称H是G的导出子图。若图G不含H为导出子图，则称H是G的禁用子图。设u,v∈V(G)，若uv∈E(G)则称顶点u和v相邻，且u，v互为邻点；图G中v的所有邻点构成的集合称为v的邻点集，记为NG(v)。

设G是一个图，对于顶点子集A⊆V(G)，用G[A]表示图G中由A导出的子图。如果E(G[A])=Ø，则称A为图G的一个独立集。如果G[A]为完全图，则称A为图G的一个团。图G中最大团的阶数称为G的团数，记为ω(G)。对于图G，如果存在映射 f:V(G)→{1，2，…，k}使得对任意的 uv∈E(G)都有f（u）≠f（v），则称G是k-可着色；使得图G有k-可着色的最小的正整数k称为G的色数，用 χ(G)表示。

不重复的点边交错序列称为路，n个顶点的路记为Pn。若图G中任意两个顶点之间都有路相连，则称G为连通图。图中与某一顶点相邻的顶点数目称为该顶点的度，连通且每个顶点的度都为2的图称为圈，不含圈的连通图称为树，森林为某些树的不交并。

本文中考虑的图都是有限简单图，文中涉及到但未给出的概念和记号可参考文献[7,14]。

2 禁用子图为P3∪P2的图着色

3 禁用子图为P3∪mP2的图着色

4 结语

根据强完美图定理可知完美图的禁用子图是奇长圈及其补图。 1987 年 Gyárfás[6]提出一系列的具有禁用子图的色界函数的猜想，并引起图论学者的广泛研究。Wagon[9]早在1980年就给出了禁用子图为2P2的图的一个色界函数，虽然这个色界函数不是紧的，但是四十年来一直没有被改进，足以说明寻找色界函数的难度。本文首先借鉴Wagon的方法给出禁用子图为P3∪P2的图的色界函数，进而得到了禁用子图为P3∪mP2的图类的色数上界，说明了Gyárfás猜想（猜想1）在F为特殊森林时是成立的。