The conjunction of the linear arboricity conjecture and Lovász's path partition theorem

• Published in: Discrete mathematics 2021-08, Vol.344 (8), p.112434, Article 112434
• Main Authors: Chen, Guantao, Hao, Yanli
• Format: Article
• Language: English
• Subjects: Dense random graphs; Gallai's path partition conjecture; k-degenerate graph; Linear arboricity conjecture
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2021.112434

A graph is a linear forest if each of its components is a path. Given a graph G with maximum degree Δ(G), motivated by the famous linear arboricity conjecture and Lovász's classic result on partitioning the edge set of a graph into paths, we call a partition F:=F1|⋯|Fk of the edge set of G an exact linear forest partition if each Fi induces a linear forest, k≤⌈Δ(G)+12⌉, and every vertex v∈V(G) is on at most ⌈dG(v)+12⌉ non-trivial paths belonging to F. In this paper, we prove the following two results.•Every 2-degenerate graph has an exact linear forest partition, and so does every series-parallel graph, every outerplanar graph, and every subdivision of any graph provided each edge of the original graph is subdivided at least once.•Let p∈(0,1) be a constant. If G∼Gn,p, then a.a.s. G has an exact linear forest partition.