INDUCED MATCHINGS IN GRAPHS OF DEGREE AT MOST 4.

For a graph G, let νs(G) be the strong matching number of G. We prove the sharp bound ν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, νs(G) ≥ m(G)/18 for such graphs and νs(G) ≥ 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 χ's(G) of a graph G is at most 5/4Δ(G)², since νs(G) ≥ m(G)/χ's(G) and n(G) ≥ 2m(G)/Δ(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size. [ABSTRACT FROM AUTHOR]