In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.
- Bounded maximum degree
- Planar graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics