pipette
ENEnglish

Hardness of Coloring -Colorable -Uniform Hypergraphs with Colors

Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 20 pages