Antipaths in oriented graphs
Preprint
Abstract
We show that for any natural number $k \ge 1$, any oriented graph $D$ of minimum semidegree at least $(3k- 2)/4$ contains an antidirected path of length $k$. In fact, a slightly weaker condition on the semidegree sequence of $D$ suffices, and as a consequence, we confirm a weakened antidirected path version of a conjecture of Addario-Berry, Havet, Linhares Sales, Thomass\'e and Reed.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Antidirected subgraphs of oriented graphsCombinatorics, Probability and Computing, 2024
- Oriented trees in digraphsDiscrete Mathematics, 2013
- Arbitrary Orientations of Hamilton Cycles in Oriented GraphsThe Electronic Journal of Combinatorics, 2011
- An exact minimum degree condition for Hamilton cycles in oriented graphsJournal of the London Mathematical Society, 2008
- A Dirac-Type Result on Hamilton Cycles in Oriented GraphsCombinatorics, Probability and Computing, 2008
- Oriented hamilton cycles in digraphsJournal of Graph Theory, 1995
- Hamilton Cycles in Oriented GraphsCombinatorics, Probability and Computing, 1993
- Long paths and cycles in oriented graphsJournal of Graph Theory, 1981