Informace o publikaci
Coloring mixed hypertrees
| Autoři | |
|---|---|
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Applied Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.dam.2005.05.019 |
| Klíčová slova | graph coloring; mixed hypergraphs; hypertrees |
| Popis | A mixed hypergraph is a triple (V, C, D) where V is its vertex set and 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 Vs 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 hypetrees 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 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. (c) 2005 Elsevier B.V. All tights reserved. |