An Iterative Approach to the Traceability Conjecture for Oriented Graphs
Susan A. van Aardt, Alewyn Petrus Burger, Jean E. Dunbar, Marietjie Frick, John M. Harris, Joy Singleton · The Electronic Journal of Combinatorics · 2013
A digraph is $k$-traceable if its order is at least $k$ and each of its subdigraphs of order $k$ is traceable. The Traceability Conjecture (TC) states that for $k\geq 2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. It has been shown that for $2\leq k\leq 6$, every $k$-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every $7$-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.