Hardness of Coloring -Colorable -Uniform Hypergraphs with Colors
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