Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SCHRIJVER GRAPH:
Reports tagged with Schrijver Graph:
TR18-073 | 21st April 2018
Amey Bhangale

#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

ISSN 1433-8092 | Imprint