The linear arboricity of some regular graphs. (English) Zbl 0581.05017

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.


05C05 Trees
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Akiyama, TRU Math. 16 pp 97– (1980)
[2] Akiyama, Math. Slovaca 30 pp 405– (1980)
[3] Akiyama, Networks 11 pp 69– (1981)
[4] Extremal Graph Theory. Academic, New York (1978).
[5] Graph Theory. Addison-Wesley, Reading, MA (1969).
[6] Harary, Ann. N.Y. Acad. Sci. 175 pp 198– (1970) · Zbl 0226.05119
[7] private communication.
[8] Tomasta, Math. Slovaca 32 pp 239– (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.