Improved inapproximability results for maxclique, chromatic number and approximate graph coloring

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The inapproximability results of Maxclique, chromatic number and graph coloring were examined. The results on the problem of finding the size of largest clique and chromatic number in a graph were obtained by the PCP constructions based on Hadamard codes. The polynomial time approximation algorithm for Maxclique achieves an approximation ratio which suggests that the problem is hard to approximate. The approximate graph coloring was shown to be NP-hard for all sufficiently large color constants values.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
Pages600-609
Number of pages10
StatePublished - 2001
Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
Duration: Oct 14 2001Oct 17 2001

Other

Other42nd Annual Symposium on Foundations of Computer Science
CountryUnited States
CityLas Vegas, NV
Period10/14/0110/17/01

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Improved inapproximability results for maxclique, chromatic number and approximate graph coloring'. Together they form a unique fingerprint.

  • Cite this

    Khot, S. (2001). Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Annual Symposium on Foundations of Computer Science - Proceedings (pp. 600-609)