关于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的一……