Vis enkel innførsel

dc.contributor.authorAboulker, Pierre
dc.contributor.authorCohen, Nathann
dc.contributor.authorHavet, Frederic
dc.contributor.authorLochet, William
dc.contributor.authorMoura, Phablo F S
dc.contributor.authorThomasse, Stephan
dc.date.accessioned2020-12-23T12:42:43Z
dc.date.available2020-12-23T12:42:43Z
dc.date.created2020-02-21T12:25:42Z
dc.date.issued2019
dc.PublishedThe Electronic Journal of Combinatorics. 2019, 26 (3), P3.19.en_US
dc.identifier.issn1097-1440
dc.identifier.urihttps://hdl.handle.net/11250/2720949
dc.description.abstractIn 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.en_US
dc.language.isoengen_US
dc.relation.urihttps://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p19
dc.rightsAttribution-NoDerivatives 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by-nd/4.0/deed.no*
dc.titleSubdivisions in digraphs of large out-degree or large dichromatic numberen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2019 The Authorsen_US
dc.source.articlenumberP3.19en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doihttps://doi.org/10.37236/6521
dc.identifier.cristin1796474
dc.source.journalThe Electronic Journal of Combinatoricsen_US
dc.source.4026en_US
dc.source.143en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution-NoDerivatives 4.0 Internasjonal
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution-NoDerivatives 4.0 Internasjonal