Covering and packing in graphs IV: Linear arboricity
Authors:
Abstract
The linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.Keywords
This publication has 7 references indexed in Scilit:
- The decompositions of line graphs, middle graphs and total graphs of complete graphs into forestsDiscrete Mathematics, 1979
- The Subgraph Problem1978
- On covering the points of a graph with point disjoint pathsLecture Notes in Mathematics, 1974
- COVERING AND PACKING IN GRAPHS, I.Annals of the New York Academy of Sciences, 1970
- A formal system for information retrieval from filesCommunications of the ACM, 1970
- GRAPH THEORY1969
- Decomposition of Finite Graphs Into ForestsJournal of the London Mathematical Society, 1964