𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Long Cycles in Graphs on a Fixed Surface

✍ Scribed by Thomas Böhme; Bojan Mohar; Carsten Thomassen

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
117 KB
Volume
85
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that there exists a function a: N 0 × R + Q N such that (i) If G is a 4-connected graph of order n embedded on a surface of Euler genus g such that the face-width of G is at least a(g, e), then G can be covered by two cycles each of which has length at least (1 -e) n.

We apply this to derive lower bounds for the length of a longest cycle in a graph G on any fixed surface. Specifically, there exist functions b: N 0 Q N and c: N 0 Q R + such that for every graph G on n vertices that is embedded on a surface of Euler genus g the following statements hold:

(ii) If G is 4-connected, then G contains a collection of at most b(g) paths which cover all vertices of G, and G contains a cycle of length at least n/b(g).

Moreover, for each e > 0, every 4-connected graph G with sufficiently large face-width contains a spanning tree of maximum degree at most 3 and a 2-connected spanning subgraph of maximum degree at most 4 such that the number of vertices of degree 3 or 4 in either of these subgraphs is at most e |V(G)|.

📜 SIMILAR VOLUMES

Color-Critical Graphs on a Fixed Surface
Color-Critical Graphs on a Fixed Surface
✍ Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 420 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let S be an orientable surface other than the sphere and let k be a natural number. Then there are infinitely many k-color-critical graphs on S if and only if 3 k 5. In particular, if k 5, then there exists a polynomially

Long cycles in critical graphs
Long cycles in critical graphs
✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 3 views
Long cycles in 3-connected graphs in ori
Long cycles in 3-connected graphs in orientable surfaces
✍ Laura Sheppardson; Xingxing Yu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

## Abstract In this article, we apply a cutting theorem of Thomassen to show that there is a function __f__: N → N such that if __G__ is a 3‐connected graph on __n__ vertices which can be embedded in the orientable surface of genus __g__ with face‐width at least __f__(__g__), then __G__ contains a

Long cycles in vertex-transitive graphs
Long cycles in vertex-transitive graphs
✍ László Babai 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract We prove that every connected vertex‐transitive graph on __n__ ≥ 4 vertices has a cycle longer than (3__n__)^1/2^. The correct order of magnitude of the longest cycle seems to be a very hard question.

Long Cycles in 3-Connected Graphs
Long Cycles in 3-Connected Graphs
✍ Guantao Chen; Xingxing Yu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Moon and Moser in 1963 conjectured that if G is a 3-connected planar graph on n vertices, then G contains a cycle of length at least Oðn log 3 2 Þ: In this paper, this conjecture is proved. In addition, the same result is proved for 3-connected graphs embeddable in the projective plane, or the torus

Long cycles passing through a specified
Long cycles passing through a specified path in a graph
✍ Hirohata, Kazuhide 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 2 views

## For a graph G and an integer an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V (G)|, σ 2 (G) -s} passing through any path of length s. We generalize this result as follows. Let k ≥