Complexity Note on Mixed Hypergraphs

Abstract A mixed hypergraph H is a triple ( V, \( \mathcal{C} \), \( \mathcal{D} \) ) where V is its vertex set and \( \mathcal{C} \) and \( \mathcal{D} \) are families of subsets of V, \( \mathcal{C} \) -edges and \( \mathcal{D} \) -edges. The degree of a vertex is the number of edges in which it is contained. A vertex coloring of H is proper if each \( \mathcal{C} \) -edge contains two vertices with the same color and each \( \mathcal{D} \) -edge contains two vertices with different colors. The feasible set of H is the set of all k ’s such that there exists a proper coloring using exactly k colors. The lower (upper) chromatic number of H is the minimum (maximum) number in the feasible set. We prove that it is NP-complete to decide whether the upper chromatic number of mixed hypergraphs with maximum degree two is at least a given k. We present polynomial time algorithms for mixed hypergraphs with maximum degree two to decide their colorability, to find a coloring using the number of colors equal to the lower chromatic number and we present a 5/3-aproximation algorithm for the upper chromatic number. We further prove that it is coNP-hard to decide whether the feasible set of a given general mixed hypergraph is an interval of integers.

Authors

• Daniel Král'
• Jan Kratochvíl
• Heinz-Jürgen Voss

Keywords

No keywords are indexed for this paper.