Powers of paths and cycles in tournaments
2021
We show that for every positive integer $k$, any tournament can be partitioned into at most $2^{ck}$ $k$-th powers of paths. This result is tight up to the exponential constant. Moreover, we prove that for every $\varepsilon>0$ and every integer $k$, any tournament on $n\ge \varepsilon^{-Ck}$ vertices which is $\varepsilon$-far from being transitive contains the $k$-th power of a cycle of length $\Omega(\varepsilon n)$; both bounds are tight up to the implied constants.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
0
Citations
NaN
KQI