Two greedy consequences for maximum induced matchings
We prove that, for every integer d  with d?3 d ? 3 , there is an approximation algorithm for the maximum induced matching problem restricted to {C3,C5} { C 3 , C 5 } -free d -regular graphs with performance ratio 0.708 3  d + 0.425 , which answers a question posed by Dabrowski et al. (Theoret. Comput. Sci. 478 (2013) 3340). Furthermore, we show that every graph with m edges that is k-degenerate and of maximum degree at most d  with k<d k < d , has an induced matching with at least m/((3k?1)d?k(k+1)+1) m / ( ( 3 k ? 1 ) d ? k ( k + 1 ) + 1 ) edges.
induced matching approximation algorithm greedy algorithm strong chromatic index degenerate graph