图乘积的分数色数

孔静

(泰山学院数学与系统科学学院，山东泰安 271021)

这样我们就可以将染色问题转化成下面的整数规划问题(Ⅰ):

1 引言

自从18世纪Euler开始对图论进行研究，图论吸引了越来越多学者的目光，并且已经成为了一个十分重要的研究领域.图的染色问题是图论中一个非常重要的问题，在实际生活中有着广泛的应用.染色问题中一个非常著名的问题就是四色定理，在其被探讨的百年期间大大推动了图论的发展.

一个图G的k正常着色，是指将G的顶点分配k中颜色，使得染同一种颜色的任意两个顶点在图G中没有边相连，即等价于染同一种颜色的顶点构成了图G的一个独立点集.一个图G的正常着色所需的最小的k的值称为图G的色数，记为χ(G)=k.在人们对图的染色问题用各种方法进行研究的同时，也引申出了与图的染色问题密切相关的一些新的领域，如图的分数染色.对图的分数染色的研究最早可追溯到对图的多重染色的研究.E.Scheinerma，D.Ullman在文［1］对分数染色的问题进行了系统的阐述.在该书中，作者首先给出了对图的理论进行分数推广的方法，特别对于染色问题，引出了分数染色的概念，它是对图的染色问题的一个推广.

我们可以将染色问题转化为一个线性规划问题.因为染同一种颜色的点在图G中构成了图G的独立点集，而图的一个染色就将G的顶点集分割成由独立点集构成的集合.因此我们可以将求一个图的色数问题转化成寻找G的若干独立集，使得这些独立集的个数最少，并且满足:G的任意顶点x都至少包含在一个独立集中.我们将所有顶点和所有独立集分别进行标号，V(G)={v1，v2，…，vn}，I(G)={I1，I2，…，Im}可以得到一个0－1矩阵M=(mij)n×m(称为顶点—独立集关系的描述矩阵)，其中

这样我们就可以将染色问题转化成下面的整数规划问题(Ⅰ):

这里My≥1中的1是全1的m维列向量.

我们将上面规划的约束放宽，由要求y∈{0，1}，变为要求y≥0，这样得到一个线性规化问题(Ⅱ):

已知任意一个图的染色问题，即整数规划问题(Ⅰ)是一个NP－complete问题.而上面的线性规划问题(Ⅱ)有多项式时间的算法.设整数规划问题(Ⅰ)的最优解为y*，线性规化问题(Ⅱ)的最优解为y＊＊，显然y＊＊≤y*.这样我们可以用y＊＊对y*进行估计.因为线性规划问题(Ⅱ)的解是一个有理数，所以对任意给定一个图G，我们定义为分数色数，记为χf(G).

目前人们对分数染色的研究一般集中在两个方面，一是研究一些特殊图的分数色数，如Kneser图，循环图等及一些图的运算下的分数色数［1－4］.如对图的乘积，已经证明了对于任意的两个图G1和G2，G1和G2的分隔乘积(记为G1*G2)，G1和G2的字典序乘积(记为G1［G2］)都满足:χf(G1*G2)= χf(G1)χf(G2)≤χ(G1)χ(G2)，χf(G1［G2］)=χf(G1)χf(G2)［1］.另一方面研究一些有关图的染色的猜想是否关于图的分数着色依然成立，如Ed¨os－Faber－Lovásze猜想，Hadwiger猜想等等［1］.因此，此领域还有大量的未解决的问题有待研究.

在本文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H，我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H)，这样就可以通过图G和H本身的性质来对它们的强乘积的分数色数进行估计.

2 基本概念

对于无向图G=(V，E)，我们分别用V(G)和E(G)表示图G的顶点集合和边集合.设顶点{u，v}⊂V(G)，我们用无序顶点对uv来标记图中的一条边，记u，v是这条边的顶点，并且称u，v与该边相关联，反之亦然.与同一条边相关联的两个顶点称为是相邻的，与同一个顶点相关联的两条边也称为是相邻的.顶点重合为一点的边称为环.如果一个图的顶点集和边集都是有限集，我们称之为有限图.在本文中我们考虑的都是没有重边和环的有限的无向图.

每一对顶点都有一条边相连的图称为完全图.V(G)中一个子集称为一个团，如果该子集中任意两个点在G中都相邻.而如果S⊆V(G)中任意两点在G中都不相邻，则称S为G的一个独立集.设C是G的任意一个独立集，如果C不包含在G的其他独立集中，那么我们称C是一个极大独立集.我们用IG表示G的所有极大独立集的集合;用I(G)表示G的所有独立集集合.G中包含顶点最多的团称为最大团，其所包含顶点的个数称为G的团数，我们用ω(G)表示.G的所有团的集合我们用C(G)表示.

设顶点集V1⊂V(G)，V2⊂V(G)，则V1×V2={(v1，v2)∶v1∈V1，v2∈V2}.下面我们定义两个图G和H的几种乘积形式.G和H的强乘积，用GH表示，它是这样一个图，其顶点集是{(u，v)∶u∈V(G)，v∈V(H)}=V(G)×V(H);两个顶点(u，x)(v，y)如果满足下面三个条件中其中一条:

(1)uv∈E(G)，xy∈E(H);

(2)uv∈E(G)，x=y;

(3)u=v，xy∈E(H).

两个图G和H的分隔乘积，记为G*H，顶点集是V(G)×V(H);两个顶点(u，x)(v，y)∈E(G*H)当且仅当uv∈E(G)或者xy∈E(H).

其他的有关图论的定义和符号请参见文献［5］.

3 主要结果

我们将对强乘积图的分数色数进行讨论，证明下面的定理.

定理1任意给定两个图G和H，ω(G)ω(H)≤χf(GH)≤χ(G)χ(H).

我们首先证明两个引理.

引理1 设I，J分别为图G和H的极大独立集，则I×J一定为GH的一个极大独立集.

引理2 设C，Q分别为图G和H的最大团，则C×Q一定为GH的一个最大团，即ω(GH)= ω(G)ω(H).

证明:因为C，Q分别为图G和H的团，因此根据强乘积的定义，C×Q中的每一个顶点在GH中都是相邻的，因此C×Q一定为GH的一个团.C×Q的顶点个数为|C|×|Q|，由C，Q分别为图G和H的最大团知，C×Q的顶点个数在GH的所有团中也是最大的.因此C×Q一定为GH的一个最大团.

分隔乘积也是图乘积的一种.对于两个图G和H的分隔乘积G*H，我们已知下面的结论成立.

引理3［1］任意给定两个图G和H，则I，J分别为图G和H的极大独立集等价于I×J为G*H的一个极大独立集.

引理4［1］对于图G和H，χf(G*H)=χf(G)χf(H)≤χ(G)χ(H).

下面我们给出定理1的证明.

证明:对于图G和H，我们求χf(GH)就是求解线性规划(Ⅱ'):

设求χf(G*H)对应的线性规划(Ⅳ)为:

其中B是G*H的顶点——极大独立集关系的0－1描述矩阵.由引理1和引理3知，{I×J∶I∈IG，J∈IH}=IG*H⊆IGH，从而矩阵B是由A的若干列向量构成的子矩阵，这意味着线性规划(Ⅳ)的一个可行解一定为线性规划(Ⅲ)的可行解，因此χf(G⊗H)≤χf(G*H).又根据引理4，

故

另一方面，线性规划(Ⅲ)的对偶规划为(DⅢ):其对应的整数规划为(IDⅢ)

由矩阵A的定义知，(IDⅢ)是从G⊗H的顶点集中挑选部分顶点，使这些顶点不在同一个独立集中，也就是说在同一个团中.因此(IDⅢ)的最优值是图G⊗H的最大团所含顶点的个数，即最大团数ω(G⊗H)，因此(DⅢ)的最优值是分数最大团数，我们用ωf(G⊗H)表示，显然ωf(G⊗H)≥ω(G⊗H).又由线性规划的对偶性质知，ωf(G⊗H)=χf(G⊗H).由引理2可得

综合(1)和(2)即得:

［1］E.Scheinerma，D.Ullman.Fractional graph theory，a rational approach to graph theory［M］.New York:J.Wiley and Sons，1997.

［2］孙磊.Kneser图的分数染色的临界性［J］.物理学学报，2002，22(A)2:238－243.

［3］G.J.Chang，L.Huang，X.Zhu.The circular chromatic numbers and the fractional chromatic number of distance graphs［J］.European Journal of Combinatorics，1998，19:423－431.

［4］D.C.Fish.Fractional colorings with large denominators［J］.Journal of Graph Theory，1995，20:403－409.

［5］J.A.Bondy，U.S.R.Murty.Graph theory with applications［M］.New York:Elsevier Science Publishing Co.，Inc，1976.