pipette
ESEspañol

Hardness of Coloring -Colorable -Uniform Hypergraphs with Colors

Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles

Preprint

In the authors' words

We show that it is quasi-NP-hard to color a -colorable -uniform hypergraph on vertices using colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a -colorable -uniform hypergraph on vertices using colors.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 20 pages