Skip to content
Preprint

Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{\Omega(1)} n$ Colors

Oct 2026 · 0 citations · 14 references
Computer Science

Abstract

We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.