# A Linear Bound for the Traceability Conjecture

###
Nicolas Lichiardopol

Lycée Craponne, Salon, France

####
Susan van Aardt

University of South Africa

####
Jean. E Dunbar

Converse College, USA

####
Marietjie Frick

University of South Africa

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
An oriented graph $D$ is said to be traceable if it admits a hamiltonian path. For $k\geq 2$, an oriented graph $D$ of order at least $k$, is said to be $k$-traceable if any subset of $k$ vertices of $D$ induces a traceable oriented graph. We denote by $t(k)$ the smallest integer bigger than or equal to $k$ such that every $k$-traceable oriented graph of order at least $t(k)$ is traceable. The Traceability Conjecture states that $t(k)\leq 2k-1$ for every $k\geq 2$. (see [3]). It was proved in [2], [1] and [4] that $t(k)=k$ for $2\leq k\leq 6$, $t(7)=9$, $t(8)\leq 14$ and that $t(k)\leq 2k^2-20k+59$ for $k\geq 9$ (which is a quadratic upper bound on $t(k)$). In this paper we prove that for $k\geq 4$, any $k$-traceable orgraph of order $n\geq 6k-20$ is traceable. This is the first linear bound in the story of the Traceability Conjecture.
%----------------------------------------------------------------
\vspace{5mm}
\noindent{\bf References: }
\begin{itemize}
\item[{[1]}] S.A. van Aardt, A.P. Burger, J.E. Dunbar, M. Frick, J.M. Harris, J.E. Singleton, An iterative approach to the traceabilty conjecture for oriented Graphs, Electronic J. Combin. 20(1): P59, (2013).
\item[{[2]}] S.A van Aardt, J. E. Dunbar, M. Frick, P. Katreni\u{c}, M. H. Nielsen, O. R. Oellermann, Traceability of $k$-traceable oriented graphs,
\item[{[3]}] S.A van Aardt, J. E. Dunbar, M. Frick, M. H. Nielsen, O. R. Oellermann, A traceability conjecture for oriented graphs, Electronic. J. Combin 15(1)R150(2008).
\item[{[4]}] A.P. Burger, Computational results on the traceability of oriented graphs of small order, Electronic J. Combin. 20(4): P23, (2013).
\end{itemize}