Piercing Independent Sets in Graphs without Large Induced Matching

Abstract

Given a graph $G$, denote by $h(G)$ the smallest size of a subset of $V(G)$ which intersects every maximum independent set of $G$. We prove that any graph $G$ without induced matching of size $t$ satisfies $h(G)\le \omega(G)^{3t-3+o(1)}$. This resolves a conjecture of Hajebi, Li and Spirkl [Hitting all maximum stable sets in $P_{5}$-free graphs. J. Combin. Theory Ser. B, 165:142-163, 2024].