A linear bound towards the traceability conjecture (Q895060): Difference between revisions

Summary: 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) \leq 2k-1\) for every \(k\geq 2\) [the third author et al., ibid. 15, No. 1, Research Paper R150, 13 p. (2008; Zbl 1178.05046)]. We show that for \(k \geq 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\).