Finding Maximum Induced Matchings in Subclasses of Claw-Free andP5-Free Graphs,and in Graphs with Matching and Induced Matchingof Equal Maximum Size

In a graph G a matching is a set of edges in which no twoedges have a common endpoint. An induced matching is amatching in which no two edges are linked by an edge of G. Themaximum induced matching (abbreviated MIM) problem is to find themaximum size of an induced matching for a given graph G. Thisproblem is known to be NP-hard even on bipartite graphs or on planargraphs. We present a polynomial time algorithm which given a graphG either finds a maximum induced matching in G, or claims that thesize of a maximum induced matching in G is strictly less than thesize of a maximum matching in G. We show that the MIM problem isNP-hard on line-graphs, claw-free graphs, chair-free graphs,Hamiltonian graphs and r-regular graphs for r geq 5. On theother hand, we present polynomial time algorithms for the MIM problemon (P ₅,D _m )-free graphs, on (bull, chair)-free graphs and online-graphs of Hamiltonian graphs.