Article ID Journal Published Year Pages File Type
4657119 Journal of Combinatorial Theory, Series B 2012 30 Pages PDF
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