Large induced forests in sparse graphs

DOI10.1002/JGT.1028MaRDI QIDQ2781059zbMATH OpenOpenAlexFDO

Authors Noga Alon, Dhruv Mubayi, Robin Thomas

Publication date 3 June 2002

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

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

zbMATH Keywords

acyclic setforesttree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Large induced forests in triangle-free planar graphs
• Large induced forests in graphs
• Induced forests in bipartite planar graphs
• Problems and results in extremal combinatorics. I.
• Maximum acyclic and fragmented sets in regular graphs

Cites work

• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• Chromatic number, girth and maximal degree
• Large induced degenerate subgraphs

Cited in

(31)

• Problems and results in extremal combinatorics. I.
• Degenerate matchings and edge colorings
• Large induced forests in planar graphs with girth 4
• A better bound on the largest induced forests in triangle-free planar graph
• Large induced trees in sparse random graphs
• The integrity of a cubic graph
• Remarks on dynamic monopolies with given average thresholds
• Large induced forests in triangle-free planar graphs
• Feedback vertex sets in cubic multigraphs
• Regular independent sets
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Forest in biquartic graphs
• Improved induced matchings in sparse graphs
• Maximum induced forests in graphs of bounded treewidth
• A note on acyclic number of planar graphs
• Large induced forests in graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• Planar digraphs without large acyclic sets
• Short proofs of some extremal results
• scientific article; zbMATH DE number 2230267 (Why is no real title available?)
• Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
• Improved induced matchings in sparse graphs
• Cycle isolation of graphs with small girth
• Induced forests in some distance-regular graphs
• Some bounds on the size of maximum G-free sets in graphs
• Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
• Upper-embeddability and the decycling number of connected 4-regular graphs
• Characterizing the extremal k-girth graphs on feedback vertex set
• The decycling number of a graph with large girth embedded in a surface
• Some combinatorial algorithms on the eliminating edge feedback number of hypergraphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five

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

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