Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657119 | Journal of Combinatorial Theory, Series B | 2012 | 30 Pages |
Abstract
The class of graphs with no K3,t-minors, t⩾3, contains all planar graphs and plays an important role in graph minor theory. In 1992, Seymour and Thomas conjectured the existence of a function α(t)>0 and a constant β>0, such that every 3-connected n-vertex graph with no K3,t-minors, t⩾3, contains a cycle of length at least α(t)nβ. The purpose of this paper is to confirm this conjecture with α(t)=(1/2)t(t−1) and .
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics