Leírás
University of Szeged, Bolyai Institute, Combinatorics Seminar
Abstract.
For positive integers $n$ and $e$, let $\kappa(n,e)$ be the minimum crossing number (the standard planar crossing number) taken over all graphs with $n$ vertices and at least $e$ edges. Pach, Spencer and Tóth [Discrete and Computational Geometry 24 623-644, (2000)] showed that $\kappa(n,e) n^2/e^3$ tends to a positive constant (called midrange crossing constant) as $n\to \infty$ and $n << e << n^2$, proving a conjecture of Erdős and Guy. In this note, we extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. All these results have their analogues for rectilinear crossing numbers.
This is joint work with Josiah Reiswig, Lászlo Székely and Zhiyu Wang.