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.)

On path-cycle decompositions of triangle-free graphs

Autor(es):
Jimenez, Andrea [1] ; Wakabayashi, Yoshiko [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Valparaiso, Fac Ingn, CIMFAV, Valparaiso - Chile
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE; v. 19, n. 3 2017.
Citações Web of Science: 1
Resumo

In this work, we study conditions for the existence of length-constrained path-cycle decompositions, that is, partitions of the edge set of a graph into paths and cycles of a given minimum length. Our main contribution is the characterization of the class of all triangle-free graphs with odd distance at least 3 that admit a path-cycle decomposition with elements of length at least 4. As a consequence, it follows that Gallai's conjecture on path decomposition holds in a broad class of sparse graphs. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 11/19978-5 - Imersão de grafos em superfícies e o modelo de ising
Beneficiário:Andrea Patricia Jiménez Ramírez
Linha de fomento: Bolsas no Brasil - Pós-Doutorado