\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Guantao Chen, Yoshimi Egawa, Ken-ichi Kawarabayashi, Bojan Mohar and Katsuhiro Ota}
%
%
\medskip
\noindent
%
%
{\bf Toughness of $K_{a,t}$-Minor-free Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
The toughness of a non-complete graph $G$ is the minimum value of
$\frac{|S|}{\omega(G-S)}$ among all separating vertex sets $S\subset V(G)$,
where $\omega(G-S)\ge 2$ is the number of components of $G-S$.
It is well-known that every $3$-connected planar graph has
toughness greater than $1/2$.
Related to this property, every $3$-connected planar graph has
many good substructures, such as a spanning tree with maximum degree three,
a $2$-walk, etc.
Realizing that 3-connected planar graphs are essentially the same as
3-connected $K_{3,3}$-minor-free graphs, we consider a generalization
to $a$-connected $K_{a,t}$-minor-free graphs, where $3\le a\le t$.
We prove that there exists a positive constant $h(a,t)$ such that
every $a$-connected $K_{a,t}$-minor-free graph $G$ has toughness at least $h(a,t)$.
For the case where $a=3$ and $t$ is odd, we obtain the best possible value
for $h(3,t)$. As a corollary it is proved that every such graph of order $n$
contains a cycle of length $\Omega(\log_{h(a,t)} n)$.
\end{document}