Gallai's path decomposition conjecture for graphs with treewidth at most 3

Autor(es)

Botler, Fabio ; Sambinelli, Maycon ; Coelho, Rafael S. ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF GRAPH THEORY; v. 93, n. 3, p. 22-pg., 2019-08-16.

Resumo

A path decomposition of a graph G is a set of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph with n vertices admits a path decomposition of size at most [(n+1)/2] RIGHT FLOOR. Gallai's conjecture was verified for many classes of graphs. In particular, Lovasz (1968) verified this conjecture for graphs with at most one vertex of even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified Gallai's conjecture for graphs with maximum degree at most 5. In this paper, we verify Gallai's conjecture for graphs with treewidth at most 3. Moreover, we show that the only graphs with treewidth at most 3 that do not admit a path decomposition of size at most [n/2] are isomorphic to K-3 or K-5(-), the graph obtained from K-5 by removing an edge. (AU)

• 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
• 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: 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