### 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 ≠ K_{4}, 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 language | English (US) |
---|---|

Pages (from-to) | 113-123 |

Number of pages | 11 |

Journal | Journal of Graph Theory |

Volume | 38 |

Issue number | 3 |

DOIs | |

State | Published - Nov 2001 |

Externally published | Yes |

### 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

Alon, N., Mubayi, D., & Thomas, R. (2001). Large induced forests in sparse graphs.

*Journal of Graph Theory*,*38*(3), 113-123. https://doi.org/10.1002/jgt.1028