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

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:NR+g:\mathbb N\to\mathbb R^+ be a function. Average-degree gap conjecture. There is a function g:NR+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.

Sources & referencesView supporting material

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.