Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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]
Número total de Autores: 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
Número total de Afiliações: 6
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
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - 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
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-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
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/19179-0 - Problemas de otimização sobre partição em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Brasil - Doutorado