Decompositions of graphs into trees with bounded degree

• Fábio Botler USP
• Luiz Hoffmann UFRJ

DOI: https://doi.org/10.5753/etc.2025.8241

Abstract

A decomposition of a graph G is a set of edge-disjoint subgraphs of G that covers the edge set of G. In 1968, Gallai conjectured that every connected simple graph on n vertices can be decomposed into at most ⌈n/2⌉ elements, in which all elements are paths. In 1977, Chung verified a weaker version of this conjecture, showing that every graph on n vertices admits a decomposition into trees of size at most ⌈n/2⌉. In 2019, Botler strengthened Chung’s result by showing that every graph on n vertices can be decomposed into trees with maximum degree at most ⌈n/2⌉, while keeping a decomposition size of at most ⌈n/2⌉. In this paper, we improve Botler’s result by reducing the maximum degree to n/4 + 2.

References

Bondy, J. A. (2014). Beautiful conjectures in graph theory. Eur. J. Comb., 37:4–23.

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