A traceability conjecture for oriented graphs.
Frick, Marietjie; van Aardt, Susan A.; Dunbar, Jean E.; Nielsen, Morten H.; Oellermann, Ortrud R. — 2008
The Electronic Journal of Combinatorics [electronic only]
A traceability conjecture for oriented graphs.
Every 8-Traceable Oriented Graph Is Traceable
A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.
Page 1