Publication details

Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs

Authors

KRÁĽ Daniel KRATOCHVIL J VOSS HJ

Year of publication 2003
Type Article in Periodical
Magazine / Source Theoretical Computer Science
Citation
Doi http://dx.doi.org/10.1016/S0304-3975(02)00408-5
Keywords coloring of hypergraphs; mixed hypergraphs; approximation algorithms for coloring
Description A mixed hypergraph H is a triple (V, C, D) where V is its vertex set and C and D are families of subsets of V (C-edges and 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 C-edge contains two vertices with the same color and each 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 restrict our attention to mixed hypergraphs with maximum degree two; those with maximum degree three are not simpler than general ones. Mixed hypergraphs with maximum degree two were suggested as an interesting subclass of mixed hypergraphs in Voloshin (Austral. J. Combin. 11 (1995) 25-45). We prove that feasible sets of mixed hypergraphs with maximum degree two are intervals. We present a linear time algorithm for determining the lower chromatic number, a linear, 5/3-approximation algorithm and a polynomial 3/2-approximation algorithm for the upper chromatic number. We prove that there is no PTAS for the upper chromatic number unless P = NP. (C) 2002 Elsevier Science B.V. All rights reserved.

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

More info