On the size of matchings in 1-planar graph with high minimum degree
On the size of matchings in 1-planar graph with high minimum degree
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\geq 7$ vertices has a matching of size at least $\frac{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 \geq 36$ vertices has a matching of size at least $\frac{3n+4}{7}$, and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel.
Yuanqiu Huang、Zhangdong Ouyang、Fengming Dong
数学
Yuanqiu Huang,Zhangdong Ouyang,Fengming Dong.On the size of matchings in 1-planar graph with high minimum degree[EB/OL].(2022-07-08)[2025-08-02].https://arxiv.org/abs/2207.03747.点此复制
评论