Crossing-critical graphs with large maximum degree

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\ge 171$, by providing examples of $k$-crossing-critical graphs with arbitrarily large maximum degree.

References in corpus (1)

• Unexpected behaviour of crossing sequences

Cited by in corpus (3)

• Nested cycles in large triangulations and crossing-critical graphs
• On the pseudolinear crossing number
• On the decay of crossing numbers of sparse graphs