@inproceedings{b526028a02b8487ba38ceb6be8e8c293,
title = "Hardness of finding independent sets in almost 3-colorable graphs",
abstract = "For every ∈ > 0, and integer q ≥ 3, we show that given an N-vertex graph that has an induced q-colorable subgraph of size (1-∈)N, it is NP-hard to find an independent set of size N/q2.",
keywords = "Graph coloring, Hardness of approximation, PCPs",
author = "Irit Dinur and Subhash Khot and Will Perkins and Muli Safra",
year = "2010",
doi = "10.1109/FOCS.2010.84",
language = "English (US)",
isbn = "9780769542447",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "212--221",
booktitle = "Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010",
}