2022/07/08 by Yuanqiu Huang, Huang, Yuanqiu, Zhangdong Ouyang +3
Computer Science · #05C10 #05C35 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2207.03747
openalex publication_date 2022/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel proved that every 1-planar graph with minimum degree 3 and n≥ 7 vertices has a matching of size at least (n+12)/(7), which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and n ≥ 36 vertices has a matching of size at least (3n+4)/(7), and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel.