Premium
Long cycles in 3‐connected graphs in orientable surfaces
Author(s) -
Sheppardson Laura,
Yu Xingxing
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10051
Subject(s) - mathematics , combinatorics , graph , genus , surface (topology) , constant (computer programming) , discrete mathematics , geometry , botany , computer science , biology , programming language
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 cycle of length at least cn log 3 2 , where c is a constant not dependent on g . © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002