English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper studies $k$-claw-free graphs, exploring the connection between anextremal combinatorics question and the power of a convex program inapproximating the maximum-weight independent set in this graph class. For theextremal question, we consider the notion, that we call \textit{conditional$\chi$-boundedness} of a graph: Given a graph $G$ that is assumed to contain anindependent set of a certain (constant) size, we are interested in upperbounding the chromatic number in terms of the clique number of $G$. Thisquestion, besides being interesting on its own, has algorithmic implications(which have been relatively neglected in the literature) on the performance ofSDP relaxations in estimating the value of maximum-weight independent set.  For $k=3$, Chudnovsky and Seymour (JCTB 2010) prove that any $3$-claw-freegraph $G$ with an independent set of size three must satisfy $\chi(G) \leq 2\omega(G)$. Their result implies a factor $2$-estimation algorithm for themaximum weight independent set via an SDP relaxation (providing the firstnon-trivial result for maximum-weight independent set in such graphs via aconvex relaxation). An obvious open question is whether a similar conditional$\chi$-boundedness phenomenon holds for any $k$-claw-free graph. Our mainresult answers this question negatively. We further present some evidence thatour construction could be useful in studying more broadly the power of convexrelaxations in the context of approximating maximum weight independent set in$k$-claw free graphs. In particular, we prove a lower bound on families ofconvex programs that are stronger than known convex relaxations usedalgorithmically in this context.

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