The 2-Decomposition Conjecture for a new class of graphs

Autor(es)

Botler, Fabio ; Jimenez, Andrea ; Sambinelli, Maycon ; Wakabayashi, Yoshiko ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 9-pg., 2021-01-01.

Resumo

The 2-Decomposition Conjecture, equivalent to the 3-Decomposition Conjecture stated in 2011 by Hoffmann-Ostenhof, claims that every connected graph G with vertices of degree 2 and 3, and satisfying that G - E(C) is disconnected for every cycle C, admits a decomposition into a spanning tree and a matching. In this work we show that the 2-Decomposition Conjecture holds for graphs whose vertices of degree 3 induce a collection of cacti in which each vertex belongs to a cycle. (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
• Beneficiário: Maycon Sambinelli
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado