On the Lovász Theta Function for Independent Sets in Sparse Graphs

DOI10.1137/15M1051002zbMath1397.05124OpenAlexW2810614232MaRDI QIDQ4571926

Anupam Gupta, Guru Prashanth Guruganesh, Nikhil Bansal

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1051002

zbMATH Keywords

Ramsey theorygraph algorithmssemidefinite programmming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (5)

Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques ⋮ On the parameterized complexity of compact set packing ⋮ On triangle-free list assignments ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ UG-hardness to NP-hardness by losing half

Cites Work

• The early evolution of the \(H\)-free process
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• On Turan's theorem for sparse graphs
• Geometric algorithms and combinatorial optimization
• Approximating the independence number via the \(\vartheta\)-function
• Coloring graphs with sparse neighborhoods
• Convex Relaxations and Integrality Gaps
• On the Lovász Theta function for Independent Sets in Sparse Graphs
• Approximation Algorithms and Semidefinite Programming
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Fast Distributed Algorithms for Brooks–Vizing Colorings
• Approximating Maximum Clique by Removing Subgraphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On the independence number of sparse graphs
• On Brooks' Theorem for Sparse Graphs
• Approximation resistance from pairwise independent subgroups
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Distributed algorithms for the Lovász local lemma and graph coloring
• Graph colouring and the probabilistic method
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Lovász Theta Function for Independent Sets in Sparse Graphs