pith. sign in

arxiv: 1610.00876 · v1 · pith:66CVLSO5new · submitted 2016-10-04 · 🧮 math.CO

Subdivisions in digraphs of large out-degree or large dichromatic number

classification 🧮 math.CO
keywords digraphcontainsdichromaticeverylargenumberout-degreesubdivision
0
0 comments X
read the original abstract

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 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.