An iterative approach to the traceability conjecture for oriented graphs
Summary: 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.
scientific article; zbMATH DE number 6171898