On feasible sets of mixed hypergraphs

KRÁĽ, Daniel. On feasible sets of mixed hypergraphs. Electronic Journal of Combinatorics. Newark, USA: ELECTRONIC JOURNAL OF COMBINATORICS, 2004, roč. 11, č. 1, 14 s. ISSN 1077-8926.

Základní údaje

Originální název

On feasible sets of mixed hypergraphs

Autoři

KRÁĽ, Daniel

Vydání

Electronic Journal of Combinatorics, Newark, USA, ELECTRONIC JOURNAL OF COMBINATORICS, 2004, 1077-8926

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

UT WoS

000220802600001

Klíčová slova anglicky

coloring of hypergraphs; mixed hypergraphs; algorithms for coloring

---

Anotace

V originále

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.