Stars and Bonds in Crossing-Critical Graphs

Warning

This publication doesn't include Faculty of Economics and Administration. 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	DOI conference
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:	Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity