Problems and Results on Colorings of Mixed Hypergraphs
Problems and Results on Colorings of Mixed Hypergraphs
复制标题
DOI：
10.1007/978-3-540-77200-2_12
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Z. Tuza;V. Voloshin
中科院分区：
文献类型：
--
作者：
Z. Tuza;V. Voloshin
我们调查的结果和开放的问题上的“混合超图”，超图与两种类型的边缘。在适当的顶点着色中，第一种类型的边不能是单色的，而第二种类型的边不能完全是多色的。虽然第一个条件仅仅意味着“经典”超图着色，但它与第二个条件的结合会导致相当不寻常的行为。例如，超图是不可着色的，或者允许着色有一定数量的k ′和k ″的颜色，但不允许着色有正好k种颜色，其中任意k ′ < k < k″。
We survey results and open problems on ‘mixed hypergraphs’ that are hypergraphs with two types of edges. In a proper vertex coloring the edges of the first type must not be monochromatic, while the edges of the second type must not be completely multicolored. Though the first condition just means ‘classical’ hypergraph coloring, its combination with the second one causes rather unusual behavior. For instance, hypergraphs occur that are uncolorable, or that admit colorings with certain numbersk′andk″of colors but no colorings with exactly k colors for anyk′ < k < k″.