On a conjecture of Pach-Spencer-T\'oth for graph crossing numbers
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:R4XD5XZ2record.jsonopen to challenge →
classification
math.CO
keywords
crossingnumbergraphconjecturepachaddressbisectionbound
read the original abstract
The crossing number of a graph $G$ denotes the minimum number of crossings in any planar drawing of $G$. In this short note, we confirm a long-standing conjecture posed by Pach, Spencer, and T\'oth over 25 years ago, establishing an optimal lower bound on the crossing number of graphs that satisfy some monotone properties. Furthermore, we address a related open problem introduced by Pach and T\'oth in 2000, which explores the interplay between the crossing number of a graph, its degree sequence, and its bisection width.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.