| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651620 | Electronic Notes in Discrete Mathematics | 2015 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
