The disjoint-edge bound for geometric graphs

From papers

Let mm be a non-negative integer and GG be a geometric graph such that DJ(uv)m|DJ(uv)|\leq m for any edge uvE(G)uv\in E(G). The disjoint-edge bound. Then

E(G)1+8m+34V(G).|E(G)|\leq \frac{\sqrt{1+8m}+3}{4}\cdot |V(G)|.

The conjecture proposes a sharp-looking linear bound on the number of edges in terms of the maximum number of edges disjoint from an individual edge. The source gives no resolution, so the claim remains open.

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

Nikita Chernega, Alexandr Polyanskii and Rinat Sadykov, “Disjoint edges in geometric graphs”, arXiv:2111.05425 (2022).

Solutions 0

No solutions have been posted yet.