Geodesic
A linear bound towards the traceability conjecture
Susan A. van Aardt1 ; Jean E. Dunbar2 ; Marietjie Frick1 ; Nicolas Lichiardopol3
1Department of Mathematical Sciences University of South Africa South Africa
2Department of Mathematics Converse College South Carolina, USA
3Lycee A. de Capronne Salon France
The electronic journal of combinatorics, Tome 22 (2015) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A digraph is k-traceable if its order is at least k and each of its subdigraphs of order k is traceable. An oriented graph is a digraph without 2-cycles. The 2-traceable oriented graphs are exactly the nontrivial tournaments, so k-traceable oriented graphs may be regarded as generalized tournaments. It is well-known that all tournaments are traceable. We denote by t(k) the smallest integer bigger than or equal to k such that every k-traceable oriented graph of order at least t(k) is traceable. The Traceability Conjecture states that t(k) ≤ 2k-1 for every k ≥ 2 [van Aardt, Dunbar, Frick, Nielsen and Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin., 15(1):#R150, 2008]. We show that for k ≥ 2, every k-traceable oriented graph with independence number 2 and order at least 4k-12 is traceable. This is the last open case in giving an upper bound for t(k) that is linear in k.
DOI : 10.37236/4727
Classification : 05C20, 05C38
Mots-clés : oriented graph, generalized tournament, \(k\)-traceable, traceability conjecture, path partition conjecture

Susan A. van Aardt  1   ; Jean E. Dunbar  2   ; Marietjie Frick  1   ; Nicolas Lichiardopol  3

1 Department of Mathematical Sciences University of South Africa South Africa
2 Department of Mathematics Converse College South Carolina, USA
3 Lycee A. de Capronne Salon France 
@article{10_37236_4727,
     author = {Susan A. van Aardt and Jean E. Dunbar and Marietjie Frick and Nicolas Lichiardopol},
     title = {A linear bound towards the traceability conjecture},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {4},
     doi = {10.37236/4727},
     zbl = {1326.05058},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4727/}
}
TY  - JOUR
AU  - Susan A. van Aardt
AU  - Jean E. Dunbar
AU  - Marietjie Frick
AU  - Nicolas Lichiardopol
TI  - A linear bound towards the traceability conjecture
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4727/
DO  - 10.37236/4727
ID  - 10_37236_4727
ER  - 
%0 Journal Article
%A Susan A. van Aardt
%A Jean E. Dunbar
%A Marietjie Frick
%A Nicolas Lichiardopol
%T A linear bound towards the traceability conjecture
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4727/
%R 10.37236/4727
%F 10_37236_4727
Susan A. van Aardt; Jean E. Dunbar; Marietjie Frick; Nicolas Lichiardopol. A linear bound towards the traceability conjecture. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/4727

Cité par Sources :