On a conjecture of Pach-Spencer-Tóth for graph crossing numbers
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |