Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

For every $eps > 0$, and integer $q geq 3$, we show that given an $N$-vertex graph that has an induced $q$-colorable subgraph of size $(1-eps)N$, it is NP-hard to find an independent set of size $ frac{N}{q^2}$.

Questions and Answers

You need to be logged in to be able to post here.