Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function

DOI10.1007/BF01196133zbMath0880.05032MaRDI QIDQ1375058

Uriel Feige

Publication date: 5 January 1998

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

graphchromatic numberNP-hardgraph productlargest independent setLovász \(\theta\)-function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Related Items

Towards optimal lower bounds for clique and chromatic number., On the approximability of clique and related maximization problems, On the limits of depth reduction at depth 3 over small finite fields, Unnamed Item, Approximation algorithms for intersection graphs, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Gap, cosum and product properties of the θ′ bound on the clique number, Heuristics for semirandom graph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection theorems with geometric consequences
• On the complexity of approximating the independent set problem
• On the ratio of optimal integral and fractional covers
• The sandwich theorem
• Approximating the independence number via the \(\vartheta\)-function
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• New approximation algorithms for graph coloring
• On the hardness of approximating minimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interactive proofs and the hardness of approximating cliques
• Probability Inequalities for Sums of Bounded Random Variables
• On cliques in graphs