3一致C-超图的最小边数  

The Minimum Number of C-Edges of 3-Uniform C-Hypergraphs

作　　者：刁科凤[1] 赵平[1] 刘桂真[2] 

机构地区：[1]临沂师范学院数学系,临沂276005 [2]山东大学数学与系统科学学院,济南250100

出　　处：《数学物理学报（A辑）》2006年第6期948-952,共5页Acta Mathematica Scientia

基　　金：国家自然科学基金(10471078);国家博士点基金(2004042204)资助

摘　　要：混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k+1时,该下界是可以达到的．The upper chromatic number X^-（H） of a C-hypergraph H= （X, C） is the maximum number of colors that can be assigned to the vertices of H in such a way that each C ∈ C contains a monochromatic pair of vertices, This paper discusses the relationship between the lower bound of the upper chromatic numbers and the lower bound of the sizes of C-edges of a C- hypergraph and proves that the lower bound of the size of C-edges of 3-uniform C-hypergraphs given in [2] is achievable when n = 2^k ＋ 1.

关 键 词：G-超图 严格染色 上色数 点对图 

分 类 号：O157.5[理学—数学]