Ackerman's linear extremal conjecture for forbidden circle-graph matchings
Ackerman's linear extremal conjecture for forbidden circle-graph matchings
A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. A circle graph is the intersection graph of chords on a circle. A matching in a geometric graph has an intersection graph whose vertices correspond to the matching edges, with adjacency when the corresponding edges cross. Ackerman's linear extremal conjecture for forbidden circle-graph matchings. For any circle graph on vertices, there exists a constant such that every -vertex geometric graph that does not contain a matching whose intersection graph is contains at most edges. This extends the paper's established linear bound for the relevant three-vertex case and would give a uniform linear extremal bound for every fixed circle graph. The general assertion is presented as a conjecture and no resolution is supplied here.
Sources & referencesView supporting material
Primary source
Radoslav Fulek and Andrew Suk, “On disjoint crossing families in geometric graphs”, arXiv:1004.2850 (2011).
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.