Decompositions of graphs into trees with bounded degree (2025)
- Authors:
- Autor USP: BOTLER, FÁBIO HAPP - IME
- Unidade: IME
- DOI: 10.5753/etc.2025.8241
- Subjects: MATEMÁTICA DA COMPUTAÇÃO; MÉTODOS DE DECOMPOSIÇÃO; TEORIA DOS GRAFOS
- Agências de fomento:
- Language: Inglês
- Abstract: 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.
- Imprenta:
- Publisher: SBC
- Publisher place: Porto Alegre
- Date published: 2025
- Source:
- Conference titles: Encontro de Teoria da Computação - ETC
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
BOTLER, Fábio Happ e HOFFMANN, Luiz. Decompositions of graphs into trees with bounded degree. 2025, Anais.. Porto Alegre: SBC, 2025. p. 46-50. Disponível em: https://doi.org/10.5753/etc.2025.8241. Acesso em: 11 fev. 2026. -
APA
Botler, F. H., & Hoffmann, L. (2025). Decompositions of graphs into trees with bounded degree. In Anais (p. 46-50). Porto Alegre: SBC. doi:10.5753/etc.2025.8241 -
NLM
Botler FH, Hoffmann L. Decompositions of graphs into trees with bounded degree [Internet]. Anais. 2025 ; 46-50.[citado 2026 fev. 11 ] Available from: https://doi.org/10.5753/etc.2025.8241 -
Vancouver
Botler FH, Hoffmann L. Decompositions of graphs into trees with bounded degree [Internet]. Anais. 2025 ; 46-50.[citado 2026 fev. 11 ] Available from: https://doi.org/10.5753/etc.2025.8241 - On nonrepetitive colorings of paths and cycles
- Decomposição de grafos em caminhos
- Separating cycle systems
- Ramsey goodness of paths versus K3,t
- Separating the edges of a graph by cycles and by subdivisions of K4
- Biclique immersions in graphs with independence number 2
- Ramsey goodness of paths versus unbalanced graphs
- Rainbow path covers of sparse random graphs (extended abstract)
- Uma introdução à teoria extremal dos grafos: minicurso introdutório
- Independent dominating sets in planar triangulations
Informações sobre o DOI: 10.5753/etc.2025.8241 (Fonte: oaDOI API)
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3283492.pdf |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
