✦ LIBER ✦

Maximum induced forests of planar graphs

✍ Scribed by Jin Akiyama; Mamoru Watanabe

Publisher: Springer Japan
Year: 1987
Tongue: English
Weight: 80 KB
Volume: 3
Category: Article
ISSN: 0911-0119
DOI: 10.1007/bf01788541

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximum Induced Linear Forests in Outerp

Maximum Induced Linear Forests in Outerplanar Graphs

✍ Michael J. Pelsmajer 📂 Article 📅 2004 🏛 Springer Japan 🌐 English ⚖ 340 KB

Large Induced Forests in Triangle-Free P

Large Induced Forests in Triangle-Free Planar Graphs

✍ Mohammad R. Salavatipour 📂 Article 📅 2006 🏛 Springer Japan 🌐 English ⚖ 178 KB

Induced forests in cubic graphs

✍ William Staton 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 151 KB

Bounds are obtained for the number of vertices in a largest induced forest in a cubic graph with large girth. In particular, as girth increases without bound, the ratio of the number of vertices in a largest induced forest to the number of vertices in the whole graph approaches 3/4. The point arbof

Decompositions of graphs into forests wi

Decompositions of graphs into forests with bounded maximum degree

✍ Mirosław Truszczyński 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 995 KB

Truszczydski, M., Decompositions of graphs into forests with bounded maximum degree, Discrete Mathematics 98 (1991) 207-222.

On the maximum induced forests of a conn

On the maximum induced forests of a connected cubic graph without triangles

✍ Maolin Zheng; Xiaoyun Lu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 438 KB

Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. For connected simple cubic graphs G without triangles, it is shown that r(G) 3 2n/3 except for two particular graphs. This lower bound is sharp and it improves a result due to J.A. Bondy, et al. [l]. Using this

Large induced forests in sparse graphs

✍ Noga Alon; Dhruv Mubayi; Robin Thomas 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

## Abstract For a graph __G__, let __a__(__G__) denote the maximum size of a subset of vertices that induces a forest. Suppose that __G__ is connected with __n__ vertices, __e__ edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and __G__ ≠ __K__~4~, then __a__(__G__) ≥ __n__ − e/4 − 1