Frick, Marietjie; van Aardt, Susan A.; Dunbar, Jean E.; Nielsen, Morten H.; Oellermann, Ortrud R. A traceability conjecture for oriented graphs. (English) Zbl 1178.05046 Electron. J. Comb. 15, No. 1, Research Paper R150, 13 p. (2008). Summary: A (di)graph \(G\) of order \(n\) is \(k\)-traceable (for some \(k\), \(1\leq k\leq n\)) if every induced sub(di)graph of \(G\) of order \(k\) is traceable. It follows from Dirac’s degree condition for hamiltonicity that for \(k \geq 2\) every \(k\)-traceable graph of order at least \(2k-1\) is hamiltonian. The same is true for strong oriented graphs when \(k=2,3,4,\) but not when \(k\geq5\). However, we conjecture that for \(k\geq2\) every \(k\)-traceable oriented graph of order at least \(2k-1\) is traceable. The truth of this conjecture would imply the truth of an important special case of the Path Partition Conjecture for Oriented Graphs. In this paper we show the conjecture is true for \(k \leq 5\) and for certain classes of graphs. In addition we show that every strong \(k\)-traceable oriented graph of order at least \(6k-20\) is traceable. We also characterize those graphs for which all walkable orientations are \(k\)-traceable. Cited in 2 ReviewsCited in 9 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C15 Coloring of graphs and hypergraphs 05C45 Eulerian and Hamiltonian graphs Keywords:traceable graph; traceable digraph; traceability; hamiltonicity; hamiltonian graph; strong oriented graphs; path partition conjecture for oriented graphs PDFBibTeX XMLCite \textit{M. Frick} et al., Electron. J. Comb. 15, No. 1, Research Paper R150, 13 p. (2008; Zbl 1178.05046) Full Text: EuDML EMIS