✦ LIBER ✦

Maximum Induced Linear Forests in Outerplanar Graphs

✍ Scribed by Michael J. Pelsmajer

Publisher: Springer Japan
Year: 2004
Tongue: English
Weight: 340 KB
Volume: 20
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-003-0528-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximum induced forests of planar graphs

✍ Jin Akiyama; Mamoru Watanabe 📂 Article 📅 1987 🏛 Springer Japan 🌐 English ⚖ 80 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

Maximum Induced Matchings for Chordal Gr

Maximum Induced Matchings for Chordal Graphs in Linear Time

✍ Andreas Brandstädt; Chính T. Hoàng 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 263 KB

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

Maximum induced matchings in graphs

✍ Jiping Liu; Huishan Zhou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 218 KB

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1 )K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs.

Maximum induced trees in graphs

✍ Paul Erdös; Michael Saks; Vera T Sós 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 952 KB