2019/11/11 by Biedl, Therese, Wittnebel, John
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.04603
In 1979, Nishizeki and Baybars showed that every planar graph with minimum degree 3 has a matching of size (n)/(3)+c (where the constant c depends on the connectivity), and even better bounds hold for planar graphs with minimum degree 4 and 5. In this paper, we investigate similar matching-bounds for \em 1-planar graphs, i.e., graphs that can be drawn such that every edge has at most one crossing. We show that every 1-planar graph with minimum degree 3 has a matching of size at least (1)/(7)n+(12)/(7), and this is tight for some graphs. We provide similar bounds for 1-planar graphs with minimum degree 4 and 5, while the case of minimum degree 6 and 7 remains open.