Decompositions of graphs into trees with bounded degree
Resumo
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.
Referências
Botler, F. (2019). Decomposition of graphs into trees with bounded maximum degree. Matemática Contemporânea, 46:94–102.
Chung, F. (1978). On partitions of graphs into trees. Discrete Mathematics, 23(1):23–30.
Lovász, L. (1968). On covering of graphs, theory of graphs (proc. colloq., tihany, 1966).
