Coloring mixed hypertrees

详细信息    查看全文

• 作者：Daniel Krá ; l’ ; Jan Kratochví ; l ; Andrzej Proskurowski and Heinz-Jü ; rgen Voss
• 关键词：Graph coloring ; Mixed hypergraphs ; Hypertrees
• 刊名：Discrete Applied Mathematics
• 出版年：2006
• 出版时间：15 March 2006
• 年：2006
• 卷：154
• 期：4
• 页码：660-672
• 全文大小：237 K

文摘

A mixed hypergraph is a triple (V,C,D) where V is its vertex set and ee1c223f19"" title=""Click to view the MathML source"">C and D are families of subsets of V, called C-edges and D-edges, respectively. For a proper coloring, we require that each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all k's for which there exists a proper coloring using exactly k colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree.

We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by facee7adfa1f38798ea91fb5cc"" title=""Click to view the MathML source"">k colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.