Stars and Bonds in Crossing-Critical Graphs

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr SALAZAR Gelasio

Year of publication 2008
Type Article in Periodical
Magazine / Source Electronic Notes in Discrete Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
Web
Field General mathematics
Keywords crossing number; crossing-critical graph
Description The structure of all known infinite families of crossing--critical graphs has 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 paper we prove two results that revolve around this conjecture. 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 graphs with arbitrarily large maximum degree that are $2$-crossing--critical in the projective plane.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.