4一致反超图的最小边数问题(英文)  

The Minimum Edge Number of a 4-Uniform Co-Hypergraph

作　　者：禹继国[1] 刁科凤[2] 刘桂真[3] 

机构地区：[1]曲阜师范大学计算机科学学院,山东日丽276826 [2]临沂师范学院数学系,山东临沂276005 [3]山东大学数学与系统科学学院,山东济南250100

出　　处：《运筹学学报》2006年第1期95-98,共4页Operations Research Transactions

基　　金：The work is supported by NSF (10471048) of ChinaRFDP (20040422004) of Higher Education and DRF of QFNU.

摘　　要：混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．A mixed hypergraph consists of two families of subsets： the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is term the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs, i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored and the bounds of the number of co-edges of 4-uniform co-hypergraphs with certain upper chromatic numbers are given.

关 键 词：运筹学 反超图 严格着色 上色数 

分 类 号：O157.5[理学—数学] TP311.13[理学—基础数学]