Stars and Bonds in Crossing-Critical Graphs

Warning

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

Authors	HLINĚNÝ Petr SALAZAR Gelasio
Year of publication	2010
Type	Article in Periodical
Magazine / Source	Journal of Graph Theory
MU Faculty or unit	Faculty of Informatics
Citation
Web	DOI
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:	Highly Parallel and Distributed Computing Systems