Decompositions of graphs into trees with bounded degree - Botler, Fábio; Hoffmann, Luiz (Anais do Encontro de Teoria da Computação (ETC), 2025)
Uma decomposição de um grafo G é um conjunto de subgrafos aresta-disjuntos de G que cobre o conjunto de arestas de G. Em 1968, Gallai conjecturou que todo grafo simples conexo com n vértices pode ser decomposto em no máximo ⌈n/2⌉ elementos, nos quais todos os elementos são caminhos. Em 1977, Chung verificou uma versão mais fraca dessa conjectura, mostrando que todo grafo com n vértices admite uma decomposição em árvores de tamanho no máximo ⌈n/2⌉. Em 2019, Botler fortaleceu o resultado de Chung ao verificar que todo grafo com n vértices pode ser decomposto em árvores com grau máximo de no máximo ⌈n/2⌉, mantendo um tamanho de decomposição de no máximo ⌈n/2⌉. Neste artigo, melhoramos o resultado de Botler reduzindo o grau máximo para n/4 + 2.