Towards optimal lower bounds for clique and chromatic number.
type: Item
instance of: scholarly article
title: Towards optimal lower bounds for clique and chromatic number.
zbMATH Open document ID: 1042.68046
DOI: 10.1016/S0304-3975(02)00535-2
author: Lars Engebretsen
author: Jonas Holmerin
published in: Theoretical Computer Science
publication date: 2003-05-25T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1915585
zbMATH Keywords: max clique
zbMATH Keywords: min chromatic number
MaRDI profile type: Publication
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Improved non-approximability results
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Q2754129
cites work: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
cites work: A threshold of ln n for approximating set cover
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Zero knowledge and the chromatic number
cites work: Q4252726
cites work: A still better performance guarantee for approximate graph coloring
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Some optimal inapproximability results
cites work: Q4142699
cites work: On the hardness of approximating the chromatic number
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: Q4856179
cites work: A Parallel Repetition Theorem
cites work: A PCP characterization of NP with optimal amortized query complexity
cites work: On Unapproximable Versions of $NP$-Complete Problems
description: scientific article; zbMATH DE number 1915585