On path-cycle decompositions of triangle-free graphs

Autor(es)

Jimenez, Andrea ^[1] ; Wakabayashi, Yoshiko ^[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

• 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: 11/19978-5 - Imersão de Grafos em Superfícies e o Modelo de Ising
• Beneficiário: Andrea Patricia Jiménez Ramírez
• Modalidade de apoio: Bolsas no Brasil - 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