Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2405.06118 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917662583422976 |
|---|---|
| author | Sun, Timothy |
| author_facet | Sun, Timothy |
| contents | In 1972, Kainen proved a general lower bound on the crossing number of a graph in a closed surface and conjectured that this bound is tight when the graph is either a complete graph or a complete bipartite graph, and the surface is of genus close to the minimum genus of that graph. Prior to the present work, these conjectures were known to be true only for small cases and when the conjectures predict a crossing number of 0, i.e., when a triangular or quadrangular embedding was already known. We show that Kainen's conjectures are true except for the three graphs $K_9$, $K_{3,5}$, and $K_{5,5}$. We also prove nonorientable analogues of these conjectures, where the only exceptions to the general formulas are $K_7$ and $K_8$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06118 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Kainen's conjectures on surface crossing numbers Sun, Timothy Combinatorics In 1972, Kainen proved a general lower bound on the crossing number of a graph in a closed surface and conjectured that this bound is tight when the graph is either a complete graph or a complete bipartite graph, and the surface is of genus close to the minimum genus of that graph. Prior to the present work, these conjectures were known to be true only for small cases and when the conjectures predict a crossing number of 0, i.e., when a triangular or quadrangular embedding was already known. We show that Kainen's conjectures are true except for the three graphs $K_9$, $K_{3,5}$, and $K_{5,5}$. We also prove nonorientable analogues of these conjectures, where the only exceptions to the general formulas are $K_7$ and $K_8$. |
| title | On Kainen's conjectures on surface crossing numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.06118 |