Premium
The linear arboricity of some regular graphs
Author(s) -
Enomoto Hikoe,
Péroche Bernard
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080211
Subject(s) - arboricity , mathematics , combinatorics , dense graph , degeneracy (biology) , graph , 1 planar graph , discrete mathematics , chordal graph , planar graph , biology , bioinformatics
We prove that the linear arboricity of every 5‐regular graph is 3. That is, the edges of any 5‐regular graph are covered by three linear forests. We also determine the linear arboricity of 6‐regular graphs and 8‐regular graphs. These results improve the known upper bounds for the linear arboricity of graphs with given maximum degree.