A better bound on the largest induced forests in triangle-free planar graph

DOI10.1007/S00373-018-1944-2zbMATH Open1402.05047arXiv1611.04546OpenAlexW2963321585MaRDI QIDQ1756090FDOQ1756090

Authors: Hung Le 

Publication date: 11 January 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: It is well-known that there exists a triangle-free planar graph of $n$ verticess such that the largest induced forest has size at most $frac5n8$. Salavatipour proved that there is a forest of size at least $frac5n9.41$ in any triangle-free planar graph of $n$ vertices. Dross, Montassier and Pinlou improved Salavatipour's bound to $frac5n9.17$. In this work, we further improve the bound to $frac5n9$. Our technique is inspired by the recent ideas from Lukot'ka, Maz{'a}k and Zhu.

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

Recommendations

• An improved bound on the largest induced forests for triangle-free planar graphs
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• Large induced forests in planar graphs with girth 4
• Large induced forests in triangle-free planar graphs
• Large induced forests in graphs

zbMATH Keywords

triangle-free planar graphsAkiyama and Watanabe conjecturelargest induced forests

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• On acyclic colorings of planar graphs
• Large induced forests in sparse graphs
• Maximum induced forests of planar graphs
• Large induced forests in triangle-free planar graphs
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• An improved bound on the largest induced forests for triangle-free planar graphs
• Maximum 4-degenerate subgraph of a planar graph
• Induced forests in bipartite planar graphs
• Size of the largest induced forest in subcubic graphs of girth at least four and five

Cited In (14)

• Maximum induced forests in graphs of bounded treewidth
• Large induced forests in planar graphs with girth 4
• Large induced forests in graphs
• Induced 2-degenerate subgraphs of triangle-free planar graphs
• Maximum induced forests of product graphs
• On the maximum induced forests of a connected cubic graph without triangles
• Maximum induced forests of planar graphs
• The size of graphs with given feedback vertex number
• An improved bound on the largest induced forests for triangle-free planar graphs
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• Induced forests in bipartite planar graphs
• 3‐Degenerate induced subgraph of a planar graph
• Large induced forests in triangle-free planar graphs
• Cycle isolation of graphs with small girth

This page was built for publication: A better bound on the largest induced forests in triangle-free planar graph

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