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 kgreater-or-equal, slanted171, by providing examples of k-crossing-critical graphs with arbitrarily large maximum degree.

Keywords

• Crossing number
• Critical graph
• Maximum degree