The disjoint-edge bound for geometric graphs

About 5 years old · traced to

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 uv∈E(G)uv\in E(G). The disjoint-edge bound. Then

∣E(G)∣≤1+8m+34⋅∣V(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.

References

Primary source

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

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.