Induced Matchings in Graphs of Maximum Degree 4

Abstract

For a graph $G$, let ${\nu }_s(G)$ be the induced matching number of $G$. We prove the sharp bound ${\nu }_s(G)\ge \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 consequence of the well known conjecture of Erdős and Nešetřil, saying that the strong chromatic index ${\chi }_s^{\prime }(G)$ of a graph $G$ is at most $\frac{5}{4}\Delta (G{)}^2$, because ${\nu }_s(G)\ge \frac{m(G)}{{\chi }_s^{\prime }(G)}$ and $n(G)\ge \frac{m(G)\Delta (G)}{2}$. Furthermore, it is shown that there is polynomial-time algorithm that computes induced matchings of size at least $\frac{n(G)}{9}$.

12 pages

References in corpus (1)

• Induced Matchings in Graphs of Bounded Maximum Degree