Large induced forests in sparse graphs

Noga Alon, Dhruv Mubayi, Robin Thomas

Research output: Contribution to journalArticle

30 Scopus citations

Abstract

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K4, then a(G) ≥ n- e/4 - 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n - α(G))/(Δ - 1)2. Several problems remain open.

Original languageEnglish (US)
Pages (from-to)113-123
Number of pages11
JournalJournal of Graph Theory
Volume38
Issue number3
DOIs
StatePublished - Nov 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • D-degenerate graph
  • Induced forests

Fingerprint Dive into the research topics of 'Large induced forests in sparse graphs'. Together they form a unique fingerprint.

  • Cite this