Maximum induced forests of planar graphs
type: Item
instance of: scholarly article
title: Maximum induced forests of planar graphs
zbMATH Open document ID: 0653.05026
DOI: 10.1007/BF01788541
author: Jin Akiyama
author: Mamoru Watanabe
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: We propose following two conjectures: 1) If G is a planar graph of order \(n\geq 4\), then there exist \(\lceil \frac{n}{2}\rceil\) vertices in G which induce a forest. 2) If G is a planar graph of order n, then it has a stable set with \(\lceil \frac{n}{4}\rceil\) vertices.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4065012
zbMATH Keywords: planar graph
zbMATH Keywords: forest
zbMATH Keywords: stable set
MaRDI profile type: Publication
cites work: Path chromatic numbers of graphs
cites work: Large induced degenerate subgraphs
full work available at URL: https://doi.org/10.1007/bf01788541
OpenAlex ID: W1980392837
Recommended article: On maximum induced forests in graphs
Recommended article: Maximum induced forests in graphs of bounded treewidth
Recommended article: Maximum induced linear forests in outerplanar graphs
Recommended article: Large induced forests in triangle-free planar graphs
Recommended article: Induced forests in bipartite planar graphs
Recommended article: Q3575471
Recommended article: A lower bound on the order of the largest induced forest in planar graphs with high girth
Recommended article: A better bound on the largest induced forests in triangle-free planar graph
Recommended article: Q3971782
Recommended article: Maximum induced trees in graphs
description: scientific article; zbMATH DE number 4065012