A Linear Bound towards the Traceability Conjecture

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 .