2024/05/28 by Gao, Yuping, Shan, Songling · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.18494
In 1980, Akiyama, Exoo, and Harary conjectured that any graph G can be decomposed into at most \lceil(Δ(G)+1)/2\rceil linear forests. We confirm the conjecture for sufficiently large graphs with large minimum degree. Precisely, we show that for any given 0<ε <1, there exists n0 ∈ ℕ for which the following statement holds: If G is a graph on n≥ n0 vertices of minimum degree at least (1+ε )n/2, then G can be decomposed into at most \lceil(Δ(G)+1)/2\rceil linear forests.