The Hardness of 3-Uniform Hypergraph Coloring

被引：0

作者：

Irit Dinur*

Oded Regev†

Clifford Smyth‡

机构：

[1] The Hebrew University of Jerusalem,School of Computer Science and Engineering

[2] Tel-Aviv University,Department of Computer Science

[3] Carnegie Mellon University,Department of Mathematics

来源：

Combinatorica | 2005年 / 25卷

关键词：

68Q17;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c2 > c1 > 1, coloring a k-uniform c1-colorable hypergraph with c2 colors is NP-hard; the case k = 2, however, remains wide open.

引用

页码：519 / 535

页数：16