Publication details
Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs
| Authors | |
|---|---|
| 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. |