Induced Matchings in Graphs of Degree at Most 4
Felix Joos, Viet Hang Nguyen · SIAM Journal on Discrete Mathematics · 2016
For a graph $G$, let $ u_s(G)$ be the strong matching number of $G$. We prove the sharp bound $ u_s(G)\geq \frac{n(G)}{9}$ for every graph $G$ of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This result implies a strengthening of a consequence, namely, $ u_s(G)\geq \frac{m(G)}{18}$ for such graphs and $ u_s(G)\geq \frac{m(G)}{20}$ for a graph of maximum degree 4, of the well-known conjecture of Erdös and Nešetřil, which says that the strong chromatic index $\chi_s'(G)$ of a graph $G$ is at most $\frac{5}{4}\Delta(G)^2$, since $ u_s(G)\geq \frac{m(G)}{\chi_s'(G)}$ and $n(G)\geq \frac{2m(G)}{\Delta(G)}$. This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.