2025/06/13 by César Hernández-Vélez, Hernández-Vélez, César, Jan Kynčl +3 · 1 citation
Computer Science · Engineering · #05C10 #05C62 #68R10 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2506.11808
openalex publication_date 2025/06/13 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
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≤ n. Conway's conjecture remains open; the best bound known is that m≤ 1.393n. Cairns and Nikolayevsky extended this conjecture to the orientable surface Sg of genus g > 0, claiming that if a graph with n vertices and m edges has a thrackle on Sg, then m ≤ 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 Sg. 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 Sg satisfies that m ≤ 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 Km,n and Kn can be thrackled on Sg.