Premium
Stars and bonds in crossing‐critical graphs
Author(s) -
Hliněný Petr,
Salazar Gelasio
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20473
Subject(s) - combinatorics , conjecture , mathematics , bounded function , 1 planar graph , projective plane , indifference graph , simple (philosophy) , graph , discrete mathematics , plane (geometry) , strong perfect graph theorem , degree (music) , chordal graph , crossing number (knot theory) , geometry , physics , mathematical analysis , philosophy , epistemology , acoustics , correlation , intersection (aeronautics) , engineering , aerospace engineering
The structure of previous known infinite families of crossing‐critical 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 K 1, n 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 K 2, 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. J Graph Theory 65: 198–215, 2010