Discrete Mathematics & Theoretical Computer Science, Vol 10, No 3 (2008)

Font Size:  Small  Medium  Large

Progress on the Traceability Conjecture for Oriented Graphs

Marietjie Frick, Peter Katrenič


A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at least 2k-1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k=6.

Full Text: PDF PostScript