Large induced forests in sparse graphs

DOI10.1002/jgt.1028zbMath0986.05060OpenAlexW4242102268MaRDI QIDQ2781059

Dhruv Mubayi, Robin Thomas, Noga Alon

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

treeforestacyclic set

Mathematics Subject Classification ID

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

Related Items (22)

A lower bound on the order of the largest induced forest in planar graphs with high girth ⋮ Improved induced matchings in sparse graphs ⋮ Maximum induced forests in graphs of bounded treewidth ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ 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 ⋮ A note on acyclic number of planar graphs ⋮ Degenerate matchings and edge colorings ⋮ Problems and results in extremal combinatorics. I. ⋮ Large induced forests in planar graphs with girth 4 ⋮ Short Proofs of Some Extremal Results ⋮ A better bound on the largest induced forests in triangle-free planar graph ⋮ Remarks on dynamic monopolies with given average thresholds ⋮ Large induced forests in triangle-free planar graphs ⋮ Minimum size of feedback vertex sets of planar graphs of girth at least five ⋮ Feedback vertex sets in cubic multigraphs ⋮ Large Induced Forests in Graphs ⋮ Unnamed Item ⋮ The integrity of a cubic graph ⋮ Improved Induced Matchings in Sparse Graphs ⋮ Regular independent sets

Cites Work

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

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