# A Linear Bound towards the Traceability Conjecture

Keywords:
Oriented graph, Generalized tournament, k-Traceable, Traceability Conjecture, Path Partition Conjecture

### Abstract

A digraph is*k*-traceable if its order is at least

*k*and each of its subdigraphs of order

*k*is traceable. An oriented graph is a digraph without 2-cycles. The 2-traceable oriented graphs are exactly the nontrivial tournaments, so

*k*-traceable oriented graphs may be regarded as generalized tournaments. It is well-known that all tournaments are traceable. 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*) ≤

*2k-1*for every

*k*≥

*2*[van Aardt, Dunbar, Frick, Nielsen and Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin., 15(1):#R150, 2008]. We show that for

*k*≥ 2, every

*k*-traceable oriented graph with independence number 2 and order at least 4

*k-*12 is traceable. This is the last open case in giving an upper bound for

*t*(

*k*) that is linear in

*k*.