2015/07/15 by Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1507.04145
We prove that, for every integer d with d≥ 3, there is an approximation algorithm for the maximum induced matching problem restricted to \ C3,C5\-free d-regular graphs with performance ratio 0.7083d+0.425, which answers a question posed by Dabrowski et al. (Theor. Comput. Sci. 478 (2013) 33-40). Furthermore, we show that every graph with m edges that is k-degenerate and of maximum degree at most d with k