On the maximum number of edges in planar graphs of bounded degree and matching number

2022/07/07 by Lars Jaffke, Paloma T. Lima, Jaffke, Lars +1
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2207.03130

openalex publication_date 2022/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.

Related

• Counting Maximum Matchings in Planar Graphs Is Hard
• On the size of matchings in 1-planar graph with high minimum degree
• Maximum edges possible in a graph for restricted independence number, maximum degree, and maximum matching size
• On the maximum number of edges of outer k-planar graphs
• Matchings in 1-planar graphs with large minimum degree