Antipaths in oriented graphs

DOI10.1016/J.DISC.2023.113515MaRDI QIDQ6098098zbMATH OpenOpenAlexFDO

Authors Tereza Klimošová, Maya Stein

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.09876

zbMATH Keywords

antidirected pathoriented graphsemidegree

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: We show that for any natural number $kge1$, 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.

Recommendations

• scientific article; zbMATH DE number 1092941
• Longest paths and cycles in bipartite oriented graphs
• Semi-degree threshold for anti-directed Hamiltonian cycles
• Digraphs without directed path of length two or three
• scientific article; zbMATH DE number 2188371

Cites work

• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• Hamilton Cycles in Oriented Graphs
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3632516 (Why is no real title available?)
• scientific article; zbMATH DE number 1047732 (Why is no real title available?)
• Long paths and cycles in oriented graphs
• Oriented hamilton cycles in digraphs
• Oriented trees in digraphs
• Some Theorems on Abstract Graphs
• Tree containment and degree conditions

Cited in

(11)

• scientific article; zbMATH DE number 5722470 (Why is no real title available?)
• scientific article; zbMATH DE number 1092941 (Why is no real title available?)
• On finding the longest antisymmetric path in directed acyclic graphs
• Antidirected spanning closed trail in tournaments
• Antidirected subgraphs of oriented graphs
• Paths with two blocks in oriented graphs of large minimum semi-degree
• Alternating paths in oriented graphs with large semidegree
• Antidirected trees in dense digraphs
• Long antipaths and anticycles in oriented graphs
• Oriented trees in digraphs without oriented 4-cycles
• Unavoidable subgraphs in digraphs with large out-degrees

This page was built for publication: Antipaths in oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098098)