The matching bound conjecture for 1-planar graphs of minimum degree 6
The matching bound conjecture for 1-planar graphs of minimum degree 6
Let 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 and vertices. Matching bound conjecture. Every such graph has a matching of size at least
The preceding construction gives 1-planar graphs of minimum degree whose maximum matching has size at most , 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
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.