Near-perfect matching conjecture for 5-connected 1-planar graphs
Near-perfect matching conjecture for 5-connected 1-planar graphs
Let be a 5-connected 1-planar graph with 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
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.