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.


Published in:
Siam Journal On Discrete Mathematics, 30, 1, 154-165
Year:
2016
Publisher:
Philadelphia, Siam Publications
ISSN:
0895-4801
Keywords:
Laboratories:




 Record created 2016-07-19, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)