Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
type: Item
instance of: scholarly article
title: Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
DOI: 10.1007/978-3-031-49815-2_15
author: Parinya Chalermsook
author: Ameet Gadekar
author: Kamyar Khodamoradi
author: Joachim Spoerhase
publication date: 2024-07-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7883489
zbMATH Keywords: \( \chi \)-boundedness
zbMATH Keywords: convex relaxation
zbMATH Keywords: Ramsey theory
MaRDI profile type: MaRDI publication profile
cites work: Q3002828
cites work: On the Lovász Theta function for Independent Sets in Sparse Graphs
cites work: Q2721980
cites work: The triangle-free process
cites work: The early evolution of the \(H\)-free process
cites work: Q4633902
cites work: A note on fractional coloring and the integrality gap of LP for maximum weight independent set
cites work: Coloring and Maximum Weight Independent Set of Rectangles
cites work: Approximation algorithms for maximum independent set of pseudo-disks
cites work: Q5417726
cites work: Greedy local improvement and weighted set packing approximation
cites work: Claw-free graphs. VI: Colouring
cites work: Semialgebraic Proofs and Efficient Algorithm Design
cites work: Q3216686
cites work: On the complexity of approximating \(k\)-set packing
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: Q4537750
cites work: Global optimization with polynomials and the problem of moments
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Q4411289
cites work: A characterization of perfect graphs
cites work: Semidefinite programming relaxations for semialgebraic problems
cites work: A survey of χ‐boundedness
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: An improved approximation for maximum weighted \(k\)-set packing
description: scientific article; zbMATH DE number 7883489