Approximability of the upper chromatic number of hypergraphs

Bujtás, Csilla and Tuza, Zsolt (2015) Approximability of the upper chromatic number of hypergraphs. Discrete Mathematics, 338 (10). pp. 1714-1721. ISSN 0012-365X

Preview

Text 1310.7964v1.pdf Download (175kB) | Preview

Abstract

A C-coloring of a hypergraph H = (X, E) is a vertex coloring φ : X → N such that each edge E ∈ E has at least two vertices with a common color. The related parameter over(χ, -) (H), called the upper chromatic number of H, is the maximum number of colors in a C-coloring of H. A hypertree is a hypergraph which has a host tree T such that each edge E ∈ E induces a connected subgraph in T. Notations n and m stand for the number of vertices and edges, respectively, in a generic input hypergraph. We establish guaranteed polynomial-time approximation ratios for the difference n - over(χ, -) (H), which is 2 + 2 ln (2 m) on hypergraphs in general, and 1 + ln m on hypertrees. The latter ratio is essentially tight as we show that n - over(χ, -) (H) cannot be approximated within (1 - ε{lunate}) ln m on hypertrees (unless NP⊆ DTIME(nO (log log n)) ). Furthermore, over(χ, -) (H) does not have O (n1 - ε{lunate})-approximation and cannot be approximated within additive error o (n) on the class of hypertrees (unless P = NP). © 2014 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item