J 2003

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

KRÁĽ, Daniel; J KRATOCHVIL a HJ VOSS

Základní údaje

Originální název

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

Autoři

KRÁĽ, Daniel; J KRATOCHVIL a HJ VOSS

Vydání

Theoretical Computer Science, AMSTERDAM, North Holland, 2003, 0304-3975

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í

Impakt faktor

Impact factor: 0.764

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

coloring of hypergraphs; mixed hypergraphs; approximation algorithms for coloring
Změněno: 6. 11. 2020 12:38, Mgr. Darina Boukalová

Anotace

V originále

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.