Linear arboricity of random regular graphs
Colin McDiarmid, Bruce H. Reed · Random Structures and Algorithms · 1990
A linear forest is a forest in which each connected component is a path. The linear arboricity la(G) of a graph G is the least number of l inear forests required to cover the edges of G. The linear arboricity conjecture is equivalent to the assertion that for every r-regular graph G l r * l lta (G) : | , I An easy count ing argument shows here that la(G)>f. f f t " d i f f icu l ty is in establishing the upper bound. This problem has received much attention; see Alon [1]. We show here how Alon's beautiful treatment for graphs with large girth allows us easily to handle random regular graphs. By the random regular graph G,,, (where rn is even) we mean a graph picked uniformly at random from the set of a l l r- regular graphs on the ver t ices 1,2,... , n. We consider r f ixed and let n--->:n. Theorem. For any positive integer r, r(totc,,,',:l+l)--- t as n--->...