Stars and bonds in crossing-critical graphs
Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
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
published in
Research
keywords
-
Bandwidth; Bounded degree; Crossing number; Crossing-critical graph Bandwidth; Graph theory; 3-connected graph; Bounded degree; Critical graph; Crossing number; Maximum degree; Negative sides; Positive sides; Projective planes; Graphic methods
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue