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

Autor(es)

Aboulker, Pierre ^[1] ; Cohen, Nathann ^[2] ; Havet, Frederic ^[3] ; Lochet, William ^[4] ; Moura, Phablo F. S. ^[5] ; Thomasse, Stephan ^[6]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 26, n. 3 JUL 19 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 15/11930-4 - Problemas de particionamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/19179-0 - Problemas de otimização sobre partição em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Brasil - Doutorado