Bound on the number of high-degree vertices in crossing-critical graphs

A graph is kk-crossing-critical if its crossing number is at least kk, but every proper subgraph has crossing number smaller than kk. High-degree vertex conjecture. For every positive integer kk, there exists an integer D=D(k)D=D(k) such that every kk-crossing-critical graph contains at most kk vertices whose degree is larger than DD. The construction in the source produces linearly many vertices of arbitrarily large degree in relation to kk, motivating this conjecture as a proposed best-possible bound; its resolution is not given in the source.

Sources & referencesView supporting material

Primary source

Zdenek Dvorak and Bojan Mohar, “Crossing-critical graphs with large maximum degree”, arXiv:0907.1599 (2009).

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.