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.
Original language | English (US) |
---|---|
Pages (from-to) | 147-158 |
Number of pages | 12 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 94 |
Issue number | 1 |
DOIs | |
State | Published - May 2005 |
Externally published | Yes |
Keywords
- Forests
- Graph minors
- Hamiltonian cycles
- Outerplanar graphs
- Planar graphs
- Series parallel graphs
- Trees
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics