Premium
Linear arboricity of random regular graphs
Author(s) -
McDiarmid Colin,
Reed Bruce
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010405
Subject(s) - arboricity , combinatorics , mathematics , random graph , computer science , statistics , discrete mathematics , graph , planar graph
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 linear forests required to cover the edges of G. The linear arboricity conjecture is equivalent to the assertion that for every r-regular graph G