
arXiv: 1610.00876
handle: 11250/2720949
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. 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.
History, Directed graphs (digraphs), tournaments, [MATH] Mathematics [math], [INFO] Computer Science [cs], Limits and Structures in Graph Theory, Hypergraphs, 510, Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Conjecture, Graph Labeling and Dimension Problems, Degree (music), Physics, Digraph, 500, Path (computing), Acoustics, Discrete mathematics, Computer science, Programming language, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Theory and Mathematics, Archaeology, Combinatorics, Computer Science, Physical Sciences, Subdivision, Combinatorics (math.CO), Tournament, Transitive relation, Mathematics, Graph Theory and Algorithms
History, Directed graphs (digraphs), tournaments, [MATH] Mathematics [math], [INFO] Computer Science [cs], Limits and Structures in Graph Theory, Hypergraphs, 510, Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Conjecture, Graph Labeling and Dimension Problems, Degree (music), Physics, Digraph, 500, Path (computing), Acoustics, Discrete mathematics, Computer science, Programming language, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Theory and Mathematics, Archaeology, Combinatorics, Computer Science, Physical Sciences, Subdivision, Combinatorics (math.CO), Tournament, Transitive relation, Mathematics, Graph Theory and Algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
