Long cycles in graphs on a fixed surface
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}\).
- 2-connected spanning subgraphs of planar 3-connected graphs
- 2‐connected coverings of bounded degree in 3‐connected graphs
- 4-connected projective planar graphs are Hamiltonian
- A theorem on paths in planar graphs
- A Theorem on Planar Graphs
- Color-critical graphs on a fixed surface
- Convex programming and circumference of 3-connected graphs of low genus
- Disjoint paths, planarizing cycles, and spanning walks
- Embeddings of graphs with no short noncontractible cycles
- Five-coloring maps on surfaces
- Generating locally-cyclic triangulations of surfaces
- Graph minors. VII: Disjoint paths on a surface
- Graphs on surfaces
- Longest cycles in 3-connected planar graphs
- Nonhamiltonian triangulations with large connectivity and representativity
- On 2-connected spanning subgraphs with low maximum degree
- Relative lengths of paths and cycles in 3-connected graphs
- Shortness exponents of families of graphs
- Simple paths on polyhedra
- Spanning trees in locally planar triangulations
- Trees in Polyhedral Graphs
- Trees in triangulations
- On certain spanning subgraphs of embeddings with applications to domination
- Subgraphs of graphs on surfaces with high representativity
- A theorem on paths in locally planar triangulations
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Tutte paths and long cycles in circuit graphs
- Cycles in 5-connected triangulations
- Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
- Subdivisions of \(K_{5}\) in graphs embedded on surfaces with face-width at least 5
- On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs
- On Short Noncontractible Cycles in Embedded Graphs
- Long cycles in 3‐connected graphs in orientable surfaces
- A note on traversing specified vertices in graphs embedded with large representativity
- Covering nearly surface-embedded graphs with a fixed number of balls
- Chords of longest circuits in locally planar graphs
- The circumference of a graph with no \(K_{3,t}\)-minor
- 2-connected spanning subgraphs with low maximum degree in locally planar graphs
- Finding large cycles in Hamiltonian graphs
This page was built for publication: Long cycles in graphs on a fixed surface
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850617)
