Stars and bonds in crossing-critical graphs Article uri icon

abstract

  • The structure of previous known infinite families of crossingcritical graphs had led to the conjecture that crossing-critical graphs have bounded bandwidth. If true, this would imply that crossing-critical graphs have bounded degree, that is, that they cannot contain subdivisions of K1n for arbitrarily large n. In this article we prove two new results that revolve around this question. On the positive side, we show that crossing-critical graphs cannot contain subdivisions of K2,n for arbitrarily large n. On the negative side, we show that there are simple 3-connected graphs with arbitrarily large maximum degree that are 2-crossing-critical in the projective plane. Although the former conjecture is now disproved in a subsequent manuscript by Dvořák and Mohar, our results are not affected, and some interesting questions remain. Namely, can the bandwidth conjecture still be true for simple 3-connected graphs in the plane? © 2010 Wiley Periodicals, Inc.

publication date

  • 2010-01-01