maximum matching

• unknown
  • maximum matching on bipartite graphs $k$ upper bounds maximum matching by $\mathcal O(k)$ – by definition
  • vertex cover $k$ implies that maximum matching is $\mathcal O(k)$ – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
  • maximum matching $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – By definition
• https://www.graphclasses.org/classes/par_13.html
  • maximum matching – A matching in a graph is a subset of pairwise disjoint edges (any two edges that do not share an endpoint). The parameter maximum matching of a graph $G$ is the largest size of a matching in $G$.