The conjunction of the linear arboricity conjecture and Lovasz's path partition theorem

作者：Chen, Guantao; Hao, Yanli^*

来源：Discrete Mathematics, 2021, 344(8): 112434.

DOI：10.1016/j.disc.2021.112434

• Linear arboricity conjecture
• Gallai's path partition conjecture
• k-degenerate graph
• Dense random graphs

A graph is a linear forest if each of its components is a path. Given a graph G with maximum degree Delta(G), motivated by the famous linear arboricity conjecture and Lovasz's classic result on partitioning the edge set of a graph into paths, we call a partition F:=F-1 vertical bar...vertical bar F-k of the edge set of G an exact linear forest partition if each F-i induces a linear forest, k <= left perpendicular Delta(G)+1/2right perpendicular, and every vertex v is an element of V(G) is on at most left perpendiculardG(v)+1/2right perpendicular 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 is an element of(0,1) be a constant. If G similar to G(n,p), then a.a.s. G has an exact linear forest partition.