Bound on the number of high-degree vertices in crossing-critical graphs
Bound on the number of high-degree vertices in crossing-critical graphs
A graph is -crossing-critical if its crossing number is at least , but every proper subgraph has crossing number smaller than . High-degree vertex conjecture. For every positive integer , there exists an integer such that every -crossing-critical graph contains at most vertices whose degree is larger than . The construction in the source produces linearly many vertices of arbitrarily large degree in relation to , 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
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.