The matching bound conjecture for 1-planar graphs of minimum degree 6

Let NN be a fixed positive integer. A 1-planar graph is a graph that admits a drawing in which each edge is crossed at most once. Consider a 1-planar graph with minimum degree at least 66 and nNn\geq N vertices. Matching bound conjecture. Every such graph has a matching of size at least

37n+O(1).\frac{3}{7}n+O(1).

The preceding construction gives 1-planar graphs of minimum degree 66 whose maximum matching has size at most 37n+47\frac{3}{7}n+\frac{4}{7}, so the conjectured linear coefficient would be tight up to an additive constant. The source provides no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Therese Biedl and John Wittnebel, “Matchings in 1-planar graphs with large minimum degree”, arXiv:1911.04603 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.