Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws

Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1

For graphs $G$ and $H$, we say that $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Already in the early 1980s Alekseev observed that if $H$ is connected, then t…