Graph Theory Seminar
Thursday, June 4, 2009 - 11:00am
1 hour (actually 50 minutes)
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.