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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.105--113
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

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

Fichier

965-3520-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

291