### Abstract

We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm [20] colors such a graph using O(n^{1/5}) colors. Our result immediately implies that for any constants k > 2 and c_{2} > c_{1} > 1, coloring a k-uniform c_{1}-colorable hypergraph with c_{2} colors is NP-hard; leaving completely open only the k = 2 graph case. We are the first to obtain a 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.

Original language | English (US) |
---|---|

Article number | 6 |

Pages (from-to) | 33-40 |

Number of pages | 8 |

Journal | Annual Symposium on Foundations of Computer Science-Proceedings |

DOIs | |

State | Published - 2002 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'The hardness of 3-uniform hypergraph coloring'. Together they form a unique fingerprint.

## Cite this

*Annual Symposium on Foundations of Computer Science-Proceedings*, 33-40. [6]. https://doi.org/10.1109/SFCS.2002.1181880