|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
Given a digraph $D$, a subdivision of $D$ is a digraph obtained by replacing every arc $uv$ in $D$ by a directed path $P(u,v)$ from $u$ to $v$ in such that every internal vertex of $P(u,v)$ (if any) is a newly created vertex.
In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$.
This conjecture is still completely open, as the existence of $f(5)$ remains unknown.
In this talk, we give some new evidences to this conjecture.
More precisely, if $D$ is an oriented path, or an in-arborescence (i.e. a tree with all edges oriented towards the root), then every digraph with minimum out-degree large enough contains a subdivision of $D$.
Additionally, we present an overview of the main conjectures and results related to subdivisions of digraphs.
Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |