Improved hardness of approximating chromatic number. (English) Zbl 1407.68195
Raghavendra, Prasad (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 16th international workshop, APPROX 2013, and 17th international workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8096, 233-243 (2013).
Summary: We prove that for sufficiently large \(K\), it is NP-hard to color \(K\)-colorable graphs with less than \(2^{\Omega(K^{\frac13})}\) colors. This improves the previous result of \(K\) versus \(K^{\frac{1}{25}\log K}\) in [S. Khot, “Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, in: Proceedings of the 42nd annual IEEE symposium on foundations of computer science, FOCS’2001. Los Alamitos, CA: IEEE Computer Society. 600–609 (2001; doi:10.1109/SFCS.2001.959936)].
For the entire collection see [Zbl 1270.68034].
For the entire collection see [Zbl 1270.68034].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
