Thrackles on nonplanar surfaces
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908407283318784 |
|---|---|
| author | Hernández-Vélez, César Kynčl, Jan Salazar, Gelasio |
| author_facet | Hernández-Vélez, César Kynčl, Jan Salazar, Gelasio |
| contents | A thrackle is a drawing of a graph on a surface such that (i) adjacent edges only intersect at their common vertex; and (ii) nonadjacent edges intersect at exactly one point, at which they cross. Conway conjectured that if a graph with $n$ vertices and $m$ edges can be thrackled on the plane, then $m\le n$. Conway's conjecture remains open; the best bound known is that $m\le 1.393n$. Cairns and Nikolayevsky extended this conjecture to the orientable surface $S_g$ of genus $g > 0$, claiming that if a graph with $n$ vertices and $m$ edges has a thrackle on $S_g$, then $m \le n + 2g$. We disprove this conjecture. In stark contrast with the planar case, we show that for each $g>0$ there is a connected graph with $n$ vertices and $2n + 2g -8$ edges that can be thrackled on $S_g$. This leaves relatively little room for further progress involving thrackles on orientable surfaces, as every connected graph with $n$ vertices and $m$ edges that can be thrackled on $S_g$ satisfies that $m \le 2n + 4g - 2$. We prove a similar result for nonorientable surfaces. We also derive nontrivial upper and lower bounds on the minimum $g$ such that $K_{m,n}$ and $K_n$ can be thrackled on $S_g$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Thrackles on nonplanar surfaces Hernández-Vélez, César Kynčl, Jan Salazar, Gelasio Combinatorics 05C10, 68R10, 05C62 A thrackle is a drawing of a graph on a surface such that (i) adjacent edges only intersect at their common vertex; and (ii) nonadjacent edges intersect at exactly one point, at which they cross. Conway conjectured that if a graph with $n$ vertices and $m$ edges can be thrackled on the plane, then $m\le n$. Conway's conjecture remains open; the best bound known is that $m\le 1.393n$. Cairns and Nikolayevsky extended this conjecture to the orientable surface $S_g$ of genus $g > 0$, claiming that if a graph with $n$ vertices and $m$ edges has a thrackle on $S_g$, then $m \le n + 2g$. We disprove this conjecture. In stark contrast with the planar case, we show that for each $g>0$ there is a connected graph with $n$ vertices and $2n + 2g -8$ edges that can be thrackled on $S_g$. This leaves relatively little room for further progress involving thrackles on orientable surfaces, as every connected graph with $n$ vertices and $m$ edges that can be thrackled on $S_g$ satisfies that $m \le 2n + 4g - 2$. We prove a similar result for nonorientable surfaces. We also derive nontrivial upper and lower bounds on the minimum $g$ such that $K_{m,n}$ and $K_n$ can be thrackled on $S_g$. |
| title | Thrackles on nonplanar surfaces |
| topic | Combinatorics 05C10, 68R10, 05C62 |
| url | https://arxiv.org/abs/2506.11808 |