Induced Matchings In Graphs Of Degree At Most 4

For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= 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, nu(s)(G) >= m(G)/18 for such graphs and nu(s)(G) >= m(G)/20 for a graph of maximum degree 4, of the well-known conjecture of Erdos and Nesetril, which says that the strong chromatic index chi(s)'(G) of a graph G is at most 5/4 Delta(G)(2), since nu(s)(G) >= m(G)/chi(s)'(G) and n(G) >= 2m(G)/Delta(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.