Decomposing highly edge-connected graphs into paths of any given length

Autor(es)

Botler, F. ; Mota, G. O. ; Oshiro, M. T. I. ; Wakabayashi, Y.

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 122, p. 508-542, JAN 2017.
• Citações Web of Science: 7

Resumo

In 2006, Barat and Thomassen posed the following conjecture: for each tree T, there exists a natural number k(T) such that, if G is a k(T)-edge-connected graph and vertical bar E(G)vertical bar is divisible by vertical bar E(T)vertical bar, then G admits a decomposition into copies of T. This conjecture was verified for stars, some bistars, paths of length 3, 5, and 2(r) for every positive integer r. We prove that this conjecture holds for paths of any fixed length. (C) 2016 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/11431-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 11/08033-0 - Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos
• Beneficiário: Fábio Happ Botler
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/01460-8 - Decomposições de grafos
• Beneficiário: Fábio Happ Botler
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado