Large induced forests in graphs

DOI10.1002/JGT.22104MaRDI QIDQ4978444zbMATH OpenOpenAlexFDO

Authors Hong-Yu Xu, Lingsheng Shi

Publication date 10 August 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.22104

zbMATH Keywords

acyclic setgirthinduced forestplanar graphtriangle-free

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• 2-Isomorphic Graphs
• An improved bound on the largest induced forests for triangle-free planar graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Large induced degenerate subgraphs
• Large induced forests in sparse graphs
• Large induced forests in triangle-free planar graphs
• Large induced trees in \(K_r\)-free graphs
• Maximum induced forests of planar graphs
• Maximum induced trees in graphs
• Problems and results in extremal combinatorics. I.
• The decycling number of regular graphs

Cited in

(33)

• Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
• Large induced forests in planar graphs with girth 4
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Large induced trees in sparse random graphs
• On maximum induced forests in graphs
• Forests in random graphs
• Induced graphs of uniform spanning forests
• The size of graphs with given feedback vertex number
• Large induced forests in triangle-free planar graphs
• Maximum induced forests of product graphs
• Large induced forests in sparse graphs
• On the maximum orders of an induced forest, an induced tree, and a stable set
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Induced Forests in Regular Graphs with Large Girth
• An improved bound on the largest induced forests for triangle-free planar graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• Induced forests in bipartite planar graphs
• Acyclic polynomials of graphs
• Robust connectivity of graphs on surfaces
• Exact Solution Algorithms for the Chordless Cycle Problem
• The Forest Number of (n,m)-Graphs
• MIP formulations for induced graph optimization problems: a tutorial
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Cycle isolation of graphs with small girth
• Induced forests in some distance-regular graphs
• Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
• Exact algorithms for the maximum k-balanced weighted biclique problem
• On decycling and forest numbers of Cartesian products of trees
• Characterizing the extremal k-girth graphs on feedback vertex set
• On maximum induced forests of the balanced bipartite graphs
• Some combinatorial algorithms on the eliminating edge feedback number of hypergraphs
• Induced forests in cubic graphs

This page was built for publication: Large induced forests in graphs

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