Publication details

On feasible sets of mixed hypergraphs


KRÁĽ Daniel

Year of publication 2004
Type Article in Periodical
Magazine / Source Electronic Journal of Combinatorics
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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info