混合超图的染色理论  

The Coloring Theory of Mixed Hypergraphs

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

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

出　　处：《数学进展》2005年第2期145-154,共10页Advances in Mathematics（China）

基　　金：国家自然科学基金(No.19831080;No.60172003)山东省自然科学基金(No.Z2000A02)资助

摘　　要：混合超图是含有两种超边的超图,一种称为D-超边,一种称为C-超边,它们的区别主要体现在染色要求上.混合超图的染色,要求每一D-超边至少有两个点染不同的颜色,每一C-超边至少有两个点染相同的颜色.用颜色最多的染色所用的颜色数称为该混合超图的上色数,用颜色最少的染色所用的颜色数称为该混合超图的下色数.混合超图的染色理论是目前国际组合学界比较新的研究课题之一.本文主要概括介绍关于混合超图染色理论已经取得的一些成果,其中包含本文作者的研究成果.并提出了一些可供进一步研究的问题.A mixed hypergraph consists of a finite set and two families of subsets: D-edges and C-edges. In a coloring, every D-edge has at least two vertices colored differently, and every C-edge has at least two vertices of the same color. The maximum and minimum numbers of colors in a coloring are called the upper and lower chromatic numbers, respectively. This paper mainly introduces the main advancements on the coloring theory of mixed hypergraphs, including some results obtained by authors. This paper also presents some problems about this theory which are valuable to future study.

关 键 词：混合超图 严格染色 上色数 下色数 

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