王雅

摘 要： 本文主要讨论了r一致B-混合超图的可着色问题，并给出了一个可着色最大边数的下界.

关键词： 混合超图 最大边数 r一致B-混合超图

1.引言

传统图与超图的染色问题产生于19世纪并在20世纪得到了较快发展和完善，该理论主要解决的是根据一定的约束条件，将一个目标集分解成若干个子集的问题，该理论可应用于地图的染色、排序、资源的分配、数据库管理等领域.一个超图的色数就是该超图的所用颜色最少的染色所用的染色数.而很显然，所用最多的颜色数为该超图的顶点数.因此，超图的染色理论是最小定点的染色理论.

3.混合超图染色理论的主要应用

混合超图的染色理论有广泛的应用背景，可应用于以下方面：

（1）能源应用问题。由一组能源，所有能源都可以在任何时间内开通且工作时间都为一个单位时间，但有些能源不能完全开通，而有些能源不能在完全不同的时间开通，第一种类型能源组成D-超边，第二种类型组成C-超边，得到一混合超图，则改组能源的排序问题可转化为相应的混合超图的染色问题.

（2）工作排序问题。由n项工作，每项工作可在任何单位时间内完成，有些工作由于使用同一种能源，以而不能同时开始，而由于技术上的原因，有些工作又必须同时开始，第一种类型的工作组成D-超边，第二种类型的工作组成C-超边，得到一个混合超图，该工作的排序问题也可以转化为混合超图的染色问题.

混合超图的染色理论还可以应用于平行计算、数据库管理、分子生物学等其他理论.

参考文献：

[1]Tao Jiang，Dhruv Mubayi，Zaolt Tuza，Vitaly Voloshin and Douglas B，West，The Chromatic Spectrum of Mixed Hypergraphs[J].Graphs and Combinatorics，2002，8：64-74.

[2]Berge C.Graphs and Hypergraphs [M].North Holland： Amsterdam，1973.

[3]Berge C.Hypergraphs：Combinatorics of Finite Sets[M].North Holland： Amsterdam，1989.