Skip to Main content Skip to Navigation
Journal articles

Progress on the traceability conjecture for oriented graphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972339
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, April 3, 2014 - 4:16:05 PM
Last modification on : Monday, October 19, 2020 - 8:00:03 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:41:01 PM

File

965-3520-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00972339, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

283

Files downloads

897