maximum induced matching

• https://www.sciencedirect.com/science/article/pii/0166218X9290275F?via%3Dihub
  • maximum induced matching – An induced matching in a graph G is a set of edges, no two of which meet a common node or are joined by an edge of G;
• unknown
  • maximum induced matching $k$ upper bounds diameter by $\mathcal O(k)$ – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
  • maximum independent set $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – Each edge of the induced matching can host at one vertex of the independent set.
  • maximum matching $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – By definition