An $\mathcal{O}(m\log n)$ algorithm for the weighted stable set problem in claw-free graphs with $\alpha (G)\le 3$

In this paper we show how to solve the \emph{Maximum Weight Stable Set Problem} in a claw-free graph $G(V,E)$ with $\alpha (G)\le 3$ in time ${\cal O}(|E|\log|V|)$\mathrm{.}Moreprecisely,intime${\cal O}(|E|)$wecheckwhether$\alpha(G) \le 3$orproduceastablesetwithcardinalityatleast$4$; moreover, if $\alpha (G)\le 3$ we produce in time $\mathcal{O}(\mathrm{\mid }E\mathrm{\mid }\log \mathrm{\mid }V\mathrm{\mid })$ a maximum stable set of $G$. This improves the bound of $\mathcal{O}(\mathrm{\mid }E\mathrm{\mid }\mathrm{\mid }V\mathrm{\mid })$ due to Faenza et al.