Article ID Journal Published Year Pages File Type
4657183 Journal of Combinatorial Theory, Series B 2010 5 Pages PDF
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