D-完全一致混合超图不可着色的一个充要条件

A necessary and sufficient condition of D-complete uniform mixed hypergraphs uncolorable

混合超图的上,下色数与C-超边和D-超边数有着必然联系.一般地,增加C边会使下色数χ(H)增加,增加D-超边会使上色数χ(H)减小.本论文对D-完全一致混合超图进行研究,利用组合数学中分划思想及方法得到的D-完全一致混合超图不可着色的一个充要条件,对D-完全一致混合超图能否着色找到了可行的依据,进一步揭示C-超边数与上,下色数之间的关系,给出了完全一致混合超图K(n,l,m)=(X,lX,Xm)在删除若干C-超边后不可着色的一些结论.

The upper chromatic number and lower chromatic number of mixed hypergraphs closely relacted with its C-hyperedges and D-hyperedges.In general,adding one C-edges to H can increase χ（H） and adding one D-edge can decrease χ（H）,where H is a mixed hypergraph,χ（H） is the lower chromatic number and χ（H） is the upper chromatic number of H.In this artical,taking complete mixed hypergraphs as a example,further uncomer the relation of that between the number of C-hyperedges and D-hyperedges in H and chromatic number of H,and give some results on upper chromatic number and lower chromatic number of uniform mixed hypergraphs H =（X,lX-C0,mX）,obtained by deleting some C-hyperedges from complete uniform mixed hypergraphs H =（X,lX,Xm）,where C0 is a subset of C.