Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657183 | Journal of Combinatorial Theory, Series B | 2010 | 5 Pages |
Abstract
A conjecture of Richter and Salazar about graphs that are critical for a fixed crossing number k is that they have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of k. In this note we disprove these conjectures for every k⩾171, by providing examples of k-crossing-critical graphs with arbitrarily large maximum degree.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics