Article ID Journal Published Year Pages File Type
4657390 Journal of Combinatorial Theory, Series B 2006 24 Pages PDF
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