Strong inapproximability results on balanced rainbow-colorable hypergraphs
type: Item
instance of: scholarly article
title: Strong inapproximability results on balanced rainbow-colorable hypergraphs
zbMATH Open document ID: 1424.05087
author: Venkatesan Guruswami
author: Euiwoong Lee
published in: Combinatorica
publication date: 2019-02-01T00:00:00Z
review text: The problem of coloring a hypergraph with few colors is a fundamental optimization problem. A $K$-uniform hypergraph $H=(V,E)$ is said to be $k$-colorable if there exists a coloring $c:V\to \{1, \dots, k\}$ of its vertices with $k$ colors so that no hyperedge is monochromatic. The problem of determining if a $K$-uniform hypergraph is $2$- colorable is a classic NP-hard problem when $K \geq 3$. Here, the authors are interested in the question of determining whether coloring a hypergraph remains hard even if we are promised that the hypergraph admits a coloring with natural stronger properties. A coloring of a hypergraph is called rainbow if every hyperedge contains at least one vertex from each color. The coloring is called perfectly balanced when each color appears the same number of times. The main result is to prove a strong hardness result that rules out coloring a hypergraph with $O(1)$ colors even when we are given that the hypergraph has a rainbow $k$-coloring with good balance between the colors (for any $k \geq 3$).
reviewed by: Linda Lesniak
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 60E15
zbMATH DE Number: 7011196
zbMATH Keywords: hypergraph
zbMATH Keywords: $K$-uniform hyperhraph
zbMATH Keywords: rainbow $k$-coloring
MaRDI profile type: Publication
full work available at URL: s00493-016-3383-0
OpenAlex ID: W2775735346
DOI: 10.1007/S00493-016-3383-0
description: scientific article; zbMATH DE number 7011196