Publication details
On feasible sets of mixed hypergraphs
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Journal of Combinatorics |
| Citation | |
| Keywords | coloring of hypergraphs; mixed hypergraphs; algorithms for coloring |
| Description | A mixed hypergraph H is a triple (V, C, D) where V is the vertex set and C and D are families of subsets of V, called C-edges and D-edges. A vertex coloring of H is proper if each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The spectrum of H is a vector (r(1),..., r(m)) such that there exist exactly r(i) different colorings using exactly i colors, r(m) greater than or equal to 1 and there is no coloring using more than m colors. The feasible set of H is the set of all i's such that r(i) not equal 0. We construct a mixed hypergraph with O(Sigma(i) log r(i)) vertices whose spectrum is equal to (r(1),..., r(m)) for each vector of non-negative integers with r(1) = 0. We further prove that for any fixed finite sets of positive integers A(1) subset of A(2) (1 is not an element of A(2)), it is NP-hard to decide whether the feasible set of a given mixed hypergraph is equal to A(2) even if it is promised that it is either A(1) or A(2). This fact has several interesting corollaries, e. g., that deciding whether a feasible set of a mixed hypergraph is gap-free is both NP-hard and coNP-hard. |