Subdivisions in digraphs of large out-degree or la... - BV FAPESP
Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Aboulker, Pierre [1] ; Cohen, Nathann [2] ; Havet, Frederic [3] ; Lochet, William [4] ; Moura, Phablo F. S. [5] ; Thomasse, Stephan [6]
Total Authors: 6
Affiliation:
[1] PSL Univ, CNRS, Ecole Normale Super, DIENS, Paris - France
[2] CNRS, Paris - France
[3] Univ Cote Dzur, CNRS, INRIA, I3S, Nice - France
[4] Univ Bergen, Bergen - Norway
[5] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[6] Univ Lyon, LIP, ENS Lyon, CNRS, Lyon - France
Total Affiliations: 6
Document type: Journal article
Source: ELECTRONIC JOURNAL OF COMBINATORICS; v. 26, n. 3 JUL 19 2019.
Web of Science Citations: 0
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. (AU)

FAPESP's process: 15/11930-4 - Graph partitioning problems
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships abroad - Research Internship - Doctorate
FAPESP's process: 16/21250-3 - Algorithmic and structural aspects of Covering and Packing problems on graphs
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 17/22611-2 - Algorithmic and structural aspects of covering and packing problems on graphs
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
FAPESP's process: 13/19179-0 - Optimization problems on graph partitioning
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships in Brazil - Doctorate