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

DOI10.1007/BF01196133zbMath0880.05032MaRDI QIDQ1375058

No author found.

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 (8)

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

This page was built for publication: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function