A Linear Bound towards the Traceability Conjecture

作者：van Aardt Susan A^*; Dunbar Jean E; Frick Marietjie; Lichiardopol Nicolas

来源：Electronic Journal of Combinatorics, 2015, 22(4): P4.26.

DOI：10.37236/4727

• Oriented graph
• Generalized tournament
• k-traceable
• Traceability Conjecture
• Path Partition Conjecture

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.

• 出版日期2015-11-13