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 FF 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 FF on kk vertices, there exists a constant ckc_k such that every nn-vertex geometric graph that does not contain a matching whose intersection graph is FF contains at most cknc_kn 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.