Subdivisions in digraphs of large out-degree or large dichromatic number
Aboulker, Pierre; Cohen, Nathann; Havet, Frederic; Lochet, William; Moura, Phablo F S; Thomasse, Stephan
Journal article, Peer reviewed
Published version
View/ Open
Date
2019Metadata
Show full item recordCollections
- Department of Informatics [983]
- Registrations from Cristin [10590]
Original version
https://doi.org/10.37236/6521Abstract
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.