关于D-完全一致混合超图上色数的一个结论的推广

郑国彪

(青海民族学院学报编辑部,青海西宁 810000)

关于D-完全一致混合超图上色数的一个结论的推广

郑国彪

(青海民族学院学报编辑部,青海西宁 810000)

混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义.

D-完全一致混合超图;上色数;下色数

1 基本概念及引理

则K(n,l,m)称为n个顶点的完全(l,m)-一致混合超图.显然,对于给定的n,l,m,在同构的意义下恰好存在一个K(n,l,m).

定义1.2[2-3]混合超图H=(X,C,D)的存在严格i-着色的所有i中最大的i称为H的上色数,表示为(H).

定义1.3[1]如果混合超图H=(X,C,D)的顶点集X的一个i分划X=(X1,X2,…,Xi)满足:

1)每一条C-超边至少有两个顶点在同一个分划块中;

2)每一条D-超边至少有两个顶点在不同的分划块中.

则该分划被称为H的可行性分划.

显然,H的任一严格i着色都对应着某一严格i可行性分划,反之亦然.因而二者是等价的.可将H的一个可行性分划或一严格i-着色c表示为:

并用ri(H)=ri表示可行性i分划的个数.

定义1.4[1]混合超图H=(X,C,D)的顶点集X的一个子集S如果不包含任何一条C-超边(D-超边)作为其子集,则称其为C稳定的或C独立的(D稳定的或D独立的).

定义1.5[1]如果H的正常i-着色中,i种颜色都被用到,那么这一着色被称为严格的i-着色.

显然,对于可着色的混合超图H,一个正常的χ(H)-着色一定是一严格着色.

定义1.6[1]在混合超图H=(X,C,D)的任一着色c中,顶点集X的子集Y,如果满足:对任意的y1∈Y,y2∈Y,有c(y1)=c(y2),则称子集Y是单色的;如果每两点的颜色都不相同,即c(y1)/=c(y2),则称子集Y是多色的.

由混合超图正常着色的定义可知,在混合超图的任一正常着色中,D-超边一定是非单色的子集,C-超边一定是非多色的子集.

定义1.7[1]H的任意一个严格i-着色都导出一个顶点集X的i分划,每一个分划块是一非空单色子集,称为色类.

定义1.8[1]混合超图H=(X,C,D)的顶点集X的一个子集S如果不包含任何一条C-超边(D-超边)作为其子集,则称其为C稳定的或C独立的(D稳定的或D独立的).

引理1.1[4]混合超图

2 主要结果

即当p=1时,结论成立.

假设对任意p＜t结论成立.则当p=t时,即从色类X1中取出t个顶点重新分配到其它色类且保持关系|Xj1|≥|Xj2|≥…≥|Xji|.不妨设第t次从X1中取出的顶点为x′(l+k-t-r),将它重新分配到色类Xj中.并设在此之前色类X2,…,Xj-1,Xj,Xj+1,…,Xr中所包含的顶点数分别为:n2,…,nj-1,nj,nj+1,…,nr,同时在此步操作前色类X1中的顶点数为l+k-r-t+1,则此步操作后各色类中的顶点数分别是:

易知第t-1步操作后,所得可行性分划对应的s的值为:

第t步操作后,所得可行性分划对应的s的值为:

又因为根据证明开始时的约定,第t步操作后,色类X1中的顶点数(l+k-r-t)不小于

其它任何一个色类中的顶点数,即:l+k-r-t≥nj+1,从而

所以,第t步操作后,所得可行性分划对应的s的值:

即当p=t时,结论也成立.

综上可知,断言对任意自然数p都成立.

在已证上述断言的基础上,下面再来证本定理结论.

显然,由断言容易得到下述结论:

[1]V italy,Voloshin V I.Coloring Mixed Hypergraphs:Theory,A lgorithm s and App lications[M].Rhode Island: Am erican Mathem atical Society Providence,2003.

[2]Voloshin V I.Them ixed hypergraphs[J].Com put.Sci.J.Moldova,1993(1):45-52.

[3]Voloshin V I.On the Upper Chrom atic Number of a Hypergraph[M].Chisinau:Preprint of Moldova State University,1992.

[4]郑国彪.一类一致混合超图的上、下色数[J].青海师专学报,2007(5):18-22.

[5]郑国彪.关于删除若干C-超边的完全一致混合超图色数的几个结论[J].青海师专学报,2008(5):12-15.

[6]郑国彪.D-完全一致混合超图不可着色的一个充要条件[J].纯粹数学与应用数学,2011,27(3):308-312.

Generalized extend of one result of the upper chromatical number of the D-complete uniform mixed hypergraph

Zheng Guobiao
(Editer Department of Qinghai Nationalities Institutes,Xining 810000,China)

It is aimportant topic to study the upper and lower chrom atical number of them ixed hypergraphs. As the hypergraphs have a complex structure,all study on chrom atical properties of the hypergraphs are lim ited to only some special kind of hypergraphs.The com p lete uniform m ixed hypergraph is themost popular one am ong they.In this artical,a new concept that the D-com p lete uniform m ixed hypergraph was given,and further studied its the upper chrom atical number on previously a initial result basis,and ageneral result was attained.In the course of proving this conclusion,we find and prove a important predication connection with the stable set of them ixed hypergraphs,which has a im portant m ean.

the D-com plete uniform mixed hypergraphs,upper chrom atic number, lower chromatic number,extend elementary method,conjecture

O157

A

1008-5513(2012)03-0294-09

2012-02-03.

青海省自然科学基金(2001-Z-911).

郑国彪(1967-),硕士,副教授,研究方向：图论及其应用.

2010 MSC:05C78