### A Linear Bound towards the Traceability 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*.#### Keywords

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