The hardness of 3-uniform hypergraph coloring (Q2368586)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5019518
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The hardness of 3-uniform hypergraph coloring |
scientific article; zbMATH DE number 5019518 |
Statements
The hardness of 3-uniform hypergraph coloring (English)
0 references
2 January 2007
0 references
Not much is known about the hardness of the problem of approximate coloring of a hypergraph. The paper makes a step towards better understanding of the problem by proving that coloring a 3-uniform 2-colorable hypergraph with \(c\) colors is NP-hard for any constant \(c\). The proof is based on combining the layered PCP and Kneser graph and relies on high chromatic numbers of the Kneser graph and its induced subgraphs known as Schrijver graphs.
0 references
hypergraph coloring problem
0 references
computational complexity
0 references
NP-hardness
0 references
Kneser graph
0 references
0.8739189505577087
0 references
0.8718565106391907
0 references
0.868168294429779
0 references
0.8649172782897949
0 references
