4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．

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

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.