Maximum induced matchings close to maximum matchings.

Extending results of Kobler and Rotics (2003), Cameron and Walker (2005) gave a complete structural description of the graphs G where the matching number ν ( G ) equals the induced matching number ν 2 ( G ) . We present a short proof of their result and use it to study 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. [ABSTRACT FROM AUTHOR]