@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",

}