Induced forests in bipartite planar graphs

DOI10.4310/JOC.2017.V8.N1.A5MaRDI QIDQ501988zbMATH OpenFDO

Authors Yan Wang, Qiqin Xie, Xingxing Yu

Publication date 10 January 2017

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00047

zbMATH Keywords

discharging methodinduced forestplanar bipartite graph

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Abstract: Akiyama and Watanabe conjectured that every simple planar bipartite graph on $n$ vertices contains an induced forest on at least $5n/8$ vertices. We apply the discharging method to show that every simple bipartite planar graph on $n$ vertices contains an induced forest on at least $lceil(4n+3)/7ceil$ vertices.

Recommendations

• scientific article; zbMATH DE number 9665
• Maximum induced forests of planar graphs
• Large induced forests in triangle-free planar graphs
• Induced Forests in Regular Graphs with Large Girth
• On maximum induced forests in graphs
• An improved bound on the largest induced forests for triangle-free planar graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Induced forests in cubic graphs
• Large induced forests in planar graphs with girth 4
• Large induced forests in graphs

Cited in

(14)

• Cycle isolation of graphs with small girth
• Large induced forests in planar graphs with girth 4
• Induced 2-degenerate subgraphs of triangle-free planar graphs
• A better bound on the largest induced forests in triangle-free planar graph
• On maximum induced forests in graphs
• Induced graphs of uniform spanning forests
• Maximum induced forests of product graphs
• Maximum induced forests of planar graphs
• Large induced forests in sparse graphs
• The size of graphs with given feedback vertex number
• Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
• Forest in biquartic graphs
• Large induced forests in triangle-free planar graphs
• Two trees in maximal planar bipartite graphs

This page was built for publication: Induced forests in bipartite planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501988)