Abstract | ||
---|---|---|
It was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least |G|^l^o^g^"^3^2, where |G| denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function @b(t)0 for t=3, such that every 3-connected graph G with no K"3","t-minor, t=3, contains a cycle of length at least |G|^@b^(^t^). We prove that this conjecture is true with @b(t)=log"8"t"^"t"^"+"^"12. We also show that every 2-connected graph with no K"2","t-minor, t=3, contains a cycle of length at least |G|/t^t^-^1. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.jctb.2006.02.006 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
3-connected graph,g. thomas,circumference,2-connected graph,3-connected planar graph,minor,general setting,cycle,connectivity,path,connected graph,planar graph,graph minor | Wheel graph,Circumference,Combinatorics,Graph toughness,Vertex (geometry),Cycle graph,Distance-regular graph,Graph minor,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
96 | 6 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
5 | 0.51 | 16 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
G. Chen | 1 | 32 | 8.36 |
Laura Sheppardson | 2 | 11 | 2.06 |
Xingxing Yu | 3 | 577 | 68.19 |
Wenan Zang | 4 | 305 | 39.19 |