A linear bound towards the traceability conjecture (Q895060): Difference between revisions
From MaRDI portal
Latest revision as of 03:49, 11 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear bound towards the traceability conjecture |
scientific article |
Statements
A linear bound towards the traceability conjecture (English)
0 references
26 November 2015
0 references
Summary: 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) \leq 2k-1\) for every \(k\geq 2\) [the third author et al., ibid. 15, No. 1, Research Paper R150, 13 p. (2008; Zbl 1178.05046)]. We show that for \(k \geq 2\), every \(k\)-traceable oriented graph with independence number 2 and order at least 4\(k\)-12 is traceable. This is the last open case in giving an upper bound for \(t(k)\) that is linear in \(k\).
0 references
oriented graph
0 references
generalized tournament
0 references
\(k\)-traceable
0 references
traceability conjecture
0 references
path partition conjecture
0 references