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

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

Texto completo
Autor(es):
Botler, Fabio [1] ; Sambinelli, Maycon [2] ; Coelho, Rafael S. [3] ; Lee, Orlando [4]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, POB 68511, BR-21941972 Rio De Janeiro - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[3] Univ Fed Rio Grande do Sul, Inst Informat, Porto Alegre, RS - Brazil
[4] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; AUG 2019.
Citações Web of Science: 0
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 L(n+1)/2<SIC> 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 Ln/2<SIC> RIGHT FLOOR are isomorphic to K3 or K5-, the graph obtained from K5 by removing an edge. (AU)

Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
Beneficiário:Maycon Sambinelli
Linha de fomento: 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
Linha de fomento: Auxílio à Pesquisa - Temático
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
Linha de fomento: Auxílio à Pesquisa - Temático