An Iterative Approach to the Traceability Conjecture for Oriented Graphs

Abstract

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.