Large induced forests in sparse graphs

Noga Alon; Dhruv Mubayi; Robin Thomas

doi:10.1002/jgt.1028

Large induced forests in sparse graphs

Noga Alon, Dhruv Mubayi, Robin Thomas

Research output: Contribution to journal › Article › peer-review

36 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 ≠ K₄, 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)². 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	https://doi.org/10.1002/jgt.1028
State	Published - Nov 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

D-degenerate graph
Induced forests

Access to Document

10.1002/jgt.1028

Cite this

@article{57bc5ccda3e74024af4a1db6307fc819,

title = "Large induced forests in sparse graphs",

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.",

keywords = "D-degenerate graph, Induced forests",

author = "Noga Alon and Dhruv Mubayi and Robin Thomas",

year = "2001",

month = nov,

doi = "10.1002/jgt.1028",

language = "English (US)",

volume = "38",

pages = "113--123",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Large induced forests in sparse graphs

AU - Alon, Noga

AU - Mubayi, Dhruv

AU - Thomas, Robin

PY - 2001/11

Y1 - 2001/11

N2 - 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.

AB - 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.

KW - D-degenerate graph

KW - Induced forests

UR - http://www.scopus.com/inward/record.url?scp=31244435235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=31244435235&partnerID=8YFLogxK

U2 - 10.1002/jgt.1028

DO - 10.1002/jgt.1028

M3 - Article

AN - SCOPUS:31244435235

SN - 0364-9024

VL - 38

SP - 113

EP - 123

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Large induced forests in sparse graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this