Richter and Salazar's bounded-bandwidth conjecture for 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. Richter and Salazar's conjecture. For every positive integer kk, there exists an integer B(k)B(k) such that every kk-crossing-critical graph has bandwidth at most B(k)B(k). The source states that this conjecture, proposed as an open problem by Carsten Thomassen in the 1990s and formulated by Richter and Salazar, is disproved in the paper for every k171k\geq 171 by examples with arbitrarily large maximum degree; the abstract presents the two conjectures as disproved together.

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.