Oriented Cycles in Digraphs of Large Outdegree
METADATA ONLY
Loading...
Author / Producer
Date
2022-12
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ.
We prove this conjecture and answer further open questions raised by Aboulker et al.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
42 (S1)
Pages / Article No.
1145 - 1187
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)