Abstract : 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.
https://hal.inria.fr/hal-00972339
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
<>
Soumis le : jeudi 3 avril 2014 - 16:16:05
Dernière modification le : mardi 14 novembre 2017 - 01:04:29
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:41:01
Marietjie Frick, Peter Katrenič. Progress on the traceability conjecture for oriented graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.105--113. 〈hal-00972339〉
