Independent set in $k$-Claw-Free Graphs: Conditional $\chi$-boundedness and the Power of LP/SDP Relaxations

Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi +1

This paper studies $k$-claw-free graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximum-weight i…