期刊
COMBINATORICA
卷 25, 期 5, 页码 519-535出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s00493-005-0032-4
关键词
-
类别
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 0(n(1/5)) colors. Our result immediately implies that for any constants k >= 3 and c(2) > c(1) > 1, coloring a k-uniform c(1)-colorable hypergraph with C-2 colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k > 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k > 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has 'many' non-monochromatic edges.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据