Average-degree gap conjecture for simple 3-connected crossing-critical graphs
Average-degree gap conjecture for simple 3-connected crossing-critical graphs
A graph is -crossing-critical if its crossing number is at least while deleting any edge reduces the crossing number below . Let be a function. Average-degree gap conjecture. There is a function such that every sufficiently large simple, -connected, -crossing-critical graph has average degree greater than . This conjecture predicts a positive gap above average degree 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.