Near-perfect matching conjecture for 5-connected 1-planar graphs

Let GG be a 5-connected 1-planar graph with nn vertices. A matching is a set of pairwise vertex-disjoint edges.

Near-perfect matching conjecture. Every 5-connected 1-planar graph has a matching of size

n2O(1).\frac{n}{2}-O(1).

The claim is motivated by a construction of 5-connected 1-planar graphs whose independent stellation-vertices force at least two unmatched vertices in every matching, while the graphs otherwise have near-perfect matchings. Whether higher connectivity generally implies Hamiltonicity in all 1-planar graphs remains an open question.

Sources & referencesView supporting material

Primary source

Therese Biedl, “Are highly connected 1-planar graphs Hamiltonian?”, arXiv:1911.02153 (2019).

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.