Subdivisions in digraphs of large out-degree or large dichromatic number (Q2315440)

Summary: \textit{W. Mader} [Combinatorica 5, 161--165 (1985; Zbl 0576.05044)] 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 paper, we show that if \(D\) is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from \(x\) to \(y\) and a directed path from \(y\) to \(x\), then every digraph with minimum out-degree large enough contains a subdivision of \(D\). Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph \(D\) is the smallest integer \(k\) such that \(D\) can be partitioned into \(k\) acyclic subdigraphs. We show that any digraph with dichromatic number greater than \(4^m (n-1)\) contains every digraph with \(n\) vertices and \(m\) arcs as a subdivision. We show that any digraph with dichromatic number greater than \(4^m (n-1)\) contains every digraph with \(n\) vertices and \(m\) arcs as a subdivision.