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 4k-12 is traceable. This is the last open case in giving an upper bound for t(k) that is linear in k