Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516177 | Journal of Combinatorial Theory, Series B | 2005 | 12 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
József Balogh, Martin Kochol, András Pluhár, Xingxing Yu,