New results on induced matchings

AbstractA matching in a graph is a set of edges no two of which share a common vertex. A matching M is an induced matching if no edge connects two edges of M. The problem of finding a maximum induced matching is known to be NP-Complete in general and specifically for bipartite graphs and for 3-regular planar graphs. The problem has been shown to be polynomial for several classes of graphs. In this paper we generalize the results to wider classes of graphs, and improve the time complexity of previously known results