It is well-known that every maximal planar graph has a matching of size at least $\tfrac{ n+8}{ 3}$ if $n\geq 14$. In this paper, we investigate similar matching-bounds for maximal \emph{ 1-planar} graphs, i.e., graphs that can be drawn such that every edge has at most one crossing. In particular we show that every 3-connected simple-maximal 1-planar graph has a matching of size at least $\tfrac{ 2n+6}{ 5}$; the bound decreases to $\tfrac{ 3n+14}{ 10}$ if the graph need not be 3-connected. We also give (weaker) bounds when the graph comes with a fixed 1-planar drawing or is not simple. All our bounds are tight in the sense that some graph that satisfies the restrictions has no bigger matching.

Categories: math.CO cs.CG

Large Matchings in Maximal 1-planar graphs