Covering planar graphs with forests

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

doi:10.1016/j.jctb.2004.12.002

Covering planar graphs with forests

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

Research output: Contribution to journal › Article › peer-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 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	https://doi.org/10.1016/j.jctb.2004.12.002
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

Online availability

10.1016/j.jctb.2004.12.002

Library availability

Discover UIUC Full Text

Cite this

@article{6da160bca35545f0a26e1caa5d6241c3,

title = "Covering planar graphs with forests",

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 = "Forests, Graph minors, Hamiltonian cycles, Outerplanar graphs, Planar graphs, Series parallel graphs, Trees",

author = "J{\'o}zsef Balogh and Martin Kochol and Andr{\'a}s Pluh{\'a}r and Xingxing Yu",

note = "E-mail addresses: [email protected] (J. Balogh), [email protected] (M. Kochol), [email protected] (A. Pluh{\'a}r), [email protected] (X. Yu). 1M. Kochol was partially supported by Grants 2/4004/04 and APV T-51-027604 and was active at Fakulta Pr{\'i}rodn{\'y}ch Vied, {\v Z}ilinsk{\'a} Univerzita v {\v Z}iline. 2A. Pluhar was partially supported by OTKA Grant T34475. 3 Xingxing Yu was partially supported by NSF Grant DMS-9970527 and NSA Grant MDA904-03-1-0052.",

year = "2005",

month = may,

doi = "10.1016/j.jctb.2004.12.002",

language = "English (US)",

volume = "94",

pages = "147--158",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Covering planar graphs with forests

AU - Balogh, József

AU - Kochol, Martin

AU - Pluhár, András

AU - Yu, Xingxing

N1 - E-mail addresses: [email protected] (J. Balogh), [email protected] (M. Kochol), [email protected] (A. Pluhár), [email protected] (X. Yu). 1M. Kochol was partially supported by Grants 2/4004/04 and APV T-51-027604 and was active at Fakulta Prírodných Vied, Žilinská Univerzita v Žiline. 2A. Pluhar was partially supported by OTKA Grant T34475. 3 Xingxing Yu was partially supported by NSF Grant DMS-9970527 and NSA Grant MDA904-03-1-0052.

PY - 2005/5

Y1 - 2005/5

N2 - 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.

AB - 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.

KW - Forests

KW - Graph minors

KW - Hamiltonian cycles

KW - Outerplanar graphs

KW - Planar graphs

KW - Series parallel graphs

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=15444380762&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=15444380762&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2004.12.002

DO - 10.1016/j.jctb.2004.12.002

M3 - Article

AN - SCOPUS:15444380762

SN - 0095-8956

VL - 94

SP - 147

EP - 158

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Covering planar graphs with forests

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this