Average-degree gap conjecture for simple 3-connected crossing-critical graphs

About 8 years old · traced to

A graph is kk-crossing-critical if its crossing number is at least kk while deleting any edge reduces the crossing number below kk. Let g:N→R+g:\mathbb N\to\mathbb R^+ be a function. Average-degree gap conjecture. There is a function g:N→R+g:\mathbb N\to\mathbb R^+ such that every sufficiently large simple, 33-connected, kk-crossing-critical graph has average degree greater than 3+g(k)3+g(k). This conjecture predicts a positive gap above average degree 33 for sufficiently large graphs in each fixed crossing-criticality class; the source presents it as an open structural conjecture.

References

Primary source

Drago Bokal, Mojca Bračič, Marek Derňár and Petr Hliněný, “On Degree Properties of Crossing-Critical Families of Graphs”, arXiv:1803.10509 (2019).

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.