Covering planar graphs with forests

József Balogh, Martin Kochol, András Pluhár, Xingxing Yu

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)147-158
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Volume94
Issue number1
DOIs
StatePublished - May 2005
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Covering planar graphs with forests'. Together they form a unique fingerprint.

Cite this