arXiv Open Access 2013

Improved Hardness of Approximating Chromatic Number

Sangxia Huang

Lihat Sumber

Abstrak

We prove that for sufficiently large K, it is NP-hard to color K-colorable graphs with less than 2^{K^{1/3}} colors. This improves the previous result of K versus K^{O(log K)} in Khot [14].

Topik & Kata Kunci

cs.CC

Penulis (1)

Sangxia Huang

Format Sitasi

APA MLA BibTeX

Huang, S. (2013). Improved Hardness of Approximating Chromatic Number. https://arxiv.org/abs/1301.5216

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2013
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓