Two disjoint cycles in digraphs

DOI10.1002/JGT.22972MaRDI QIDQ6081571zbMATH OpenOpenAlexFDO

Authors Joanna Polcyn, Christian Reiher

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

cyclesdigraphsextremal graph theory

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Bermond and Thomassen conjectured that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex disjoint cycles. So far the conjecture was verified for $kle3$. Here we generalise the question asking for all outdegree sequences which force $k$ vertex disjoint cycles and give the full answer for $kle2$.

Recommendations

• Two vertex-disjoint cycles in a graph
• Disjoint Cycles in a Digraph with Partial Degree
• Disjoint cycles of different lengths in graphs and digraphs
• On digraphs with no two disjoint directed cycles
• Two edge-disjoint Hamiltonian cycles in graphs
• Partition and disjoint cycles in digraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• Disjoint chorded cycles in graphs
• On the existence of disjoint cycles in a graph
• Two disjoint cycles of various lengths in alternating group graph

Cites work

• A step toward the Bermond-Thomassen conjecture about disjoint cycles in digraphs
• Cycles in digraphs– a survey
• Disjoint cycles in digraphs
• Disjoint directed cycles
• On Hamilton's ideals
• On the maximal number of independent circuits in a graph
• Two proofs of Bermond-Thomassen conjecture for regular tournaments
• Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

Cited in

(14)

• On digraphs with no two disjoint directed cycles
• Disjoint directed cycles
• The Gallai-Younger conjecture for planar graphs
• Disjoint cycles of different lengths in graphs and digraphs
• Vertex disjoint 4-cycles in bipartite tournaments
• A note on disjoint dijoins
• On the problem of finding disjoint cycles and dicycles in a digraph
• Disjoint cycles with different length in 4-arc-dominated digraphs
• Vertex disjoint cycles of different length in digraphs
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles
• A step toward the Bermond-Thomassen conjecture about disjoint cycles in digraphs
• scientific article; zbMATH DE number 908792 (Why is no real title available?)
• On the number of vertex-disjoint cycles in digraphs
• Vertex-disjoint cycles in bipartite tournaments

This page was built for publication: Two disjoint cycles in digraphs

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