Crossing-critical graphs with large maximum degree
- Series
- Graph Theory Seminar
- Time
- Thursday, June 4, 2009 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Zdenek Dvorak – Simon Fraser University
Richter and Salazar conjectured that graphs that are critical for a fixed crossing number k have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of k. We disprove these conjectures for every k >170, by providing examples of k-crossing-critical graphs with arbitrarily large maximum degree, and explore the structure of such graphs.