DMS Combinatorics Seminar

Speaker: Songling Shan (Auburn  University)

Title: Linear arboricity of graphs with large minimum degree

Abstract: In 1980, Akiyama, Exoo, and Harary conjectured that any graph \(G\) can be decomposed into at most \(\lceil(\Delta(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<\varepsilon <1\), there exists  \(n_0 \in \mathbb{N}\) for which the following statement holds: If \(G\)  is a graph on \(n\ge n_0\) vertices of  minimum degree at least \((1+\varepsilon)n/2\), then \(G\) can be decomposed into at most \(\lceil(\Delta(G)+1)/2\rceil\) linear forests.  

This is joint work with Yuping Gao.