The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz

A theorem of Ding, Oporowski, Oxley, and Vertigan implies that any sufficiently large twin-free graph contains a large matching, a co-matching, or a half-graph as a semi-induced su…