The linear disjoint-matching conjecture for angularly monotone topological graphs
The linear disjoint-matching conjecture for angularly monotone topological graphs
A simple angularly monotone topological graph is a topological graph drawn on a cylinder whose base is horizontal, in which every vertical line intersects every edge at most once; it is complete when every pair of vertices is joined by an edge. A disjoint matching is a set of pairwise vertex-disjoint edges. For a graph on vertices, let the matching size be the number of edges in the matching.
Angularly monotone matching conjecture. Every simple angularly monotone complete topological graph on vertices contains a disjoint matching of size
This would be the angularly monotone analogue of the immediate linear bound for complete -monotone topological graphs, where a matching of size exists. Together with the paper's reduction from general simple complete topological graphs to cylindrical angularly monotone drawings, the conjecture could improve the known lower bound for disjoint matchings in complete simple topological graphs to a stronger bound.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Radoslav Fulek, “Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings”, arXiv:1307.4191 (2013).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.