Long cycles in graphs on a fixed surface (Q1850617)

The authors' main result states, for fixed \(g\) and \(\varepsilon\), that if \(G\) is a 4-connected graph with \(n\) vertices that has an embedding of Euler genus \(g\) and whose shortest non-contractible cycle is sufficiently large, then the vertices of \(G\) can be covered by two cycles each of which has length at least \((1 -\varepsilon)n\). From this they deduce, among other things, the existence of functions \(b(g)\) and \(c(g)\) such that if \(G\) is a graph with \(n\) vertices that is embedded on a surface of Euler genus \(g\), then (i) if \(G\) is 4-connected, \(G\) contains a collection of at most \(b(g)\) paths that cover all the vertices of \(G\) and \(G\) contains a cycle of length at least \(2n/5b(g)\); and (ii) if \(G\) is 3-connected, \(G\) contains a cycle of length at least \(c(g)n^{\log 2/\log 3}\).