Article ID Journal Published Year Pages File Type
9516177 Journal of Combinatorial Theory, Series B 2005 12 Pages PDF
Abstract
We study the problem of covering graphs with trees and a graph of bounded maximum degree. By a classical theorem of Nash-Williams, every planar graph can be covered by three trees. We show that every planar graph can be covered by two trees and a forest, and the maximum degree of the forest is at most 8. Stronger results are obtained for some special classes of planar graphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,