Induced forests in bipartite planar graphs

DOI10.4310/JOC.2017.V8.N1.A5zbMATH Open1352.05053arXiv1605.00047MaRDI QIDQ501988FDOQ501988

Authors: Yan Wang, Qiqin Xie, Xingxing Yu 

Publication date: 10 January 2017

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

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.

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

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

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)

Cited In (14)

• 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
• Maximum induced forests of product graphs
• Induced graphs of uniform spanning forests
• Maximum induced forests of planar graphs
• Large induced forests in sparse graphs
• The size of graphs with given feedback vertex number
• Forest in biquartic graphs
• Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
• Large induced forests in triangle-free planar graphs
• Two trees in maximal planar bipartite graphs
• Cycle isolation of graphs with small girth

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)