×

A traceability conjecture for oriented graphs. (English) Zbl 1178.05046

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: EuDML EMIS