Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.02301 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912219314257920 |
|---|---|
| author | Chen, Kaizhe Ma, Jie |
| author_facet | Chen, Kaizhe Ma, Jie |
| contents | 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óth 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óth in 2000, which explores the interplay between the crossing number of a graph, its degree sequence, and its bisection width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02301 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On a conjecture of Pach-Spencer-Tóth for graph crossing numbers Chen, Kaizhe Ma, Jie Combinatorics 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óth 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óth in 2000, which explores the interplay between the crossing number of a graph, its degree sequence, and its bisection width. |
| title | On a conjecture of Pach-Spencer-Tóth for graph crossing numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.02301 |