Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657390 | Journal of Combinatorial Theory, Series B | 2006 | 24 Pages |
Abstract
It was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least |G|log32, where |G| denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function β(t)>0 for t⩾3, such that every 3-connected graph G with no K3,t-minor, t⩾3, contains a cycle of length at least |G|β(t). We prove that this conjecture is true with β(t)=log8tt+12. We also show that every 2-connected graph with no K2,t-minor, t⩾3, contains a cycle of length at least |G|/tt−1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics