On Graphs with Induced Matching Number Almost Equal to Matching Number

Kobler and Rotics in 2003, and Cameron and Walker in 2005, gave a complete structural description of the graphs G where the matching number ν(G) equals the induced matching number ν2(G). We study their result and use it to analyse graphs G with ν(G)−ν2(G)≤k. We show that the recognition of these graphs can be done in polynomial time for fixed k, and is fixed parameter tractable when parameterized by k for graphs of bounded maximum degree.