The linear disjoint-matching conjecture for angularly monotone topological graphs

From papers

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 nn 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 nn vertices contains a disjoint matching of size

Ω(n).\Omega(n).

This would be the angularly monotone analogue of the immediate linear bound for complete xx-monotone topological graphs, where a matching of size n/2\left\lfloor n/2\right\rfloor exists. Together with the paper's reduction from general simple complete topological graphs to cylindrical angularly monotone drawings, the conjecture could improve the known Ω(n1/3)\Omega(n^{1/3}) 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

No solutions have been posted yet.