Richter and Salazar's bounded-bandwidth conjecture for crossing-critical graphs
Richter and Salazar's bounded-bandwidth conjecture for crossing-critical graphs
A graph is -crossing-critical if its crossing number is at least , but every proper subgraph has crossing number smaller than . Richter and Salazar's conjecture. For every positive integer , there exists an integer such that every -crossing-critical graph has bandwidth at most . 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 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
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.