Matchings in 1‐planar graphs with large minimum degree
Thérèse Biedl, John Wittnebel · Journal of Graph Theory · 2021
Abstract In 1979, Nishizeki and Baybars showed that every planar graph with minimum degree 3 has a matching of size (where the constant 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 1‐planar graphs, that is, 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 , 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.