Large induced degenerate subgraphs

N. Alon; J. Kahn; P. D. Seymour

doi:10.1007/BF01788542

Large induced degenerate subgraphs

N. Alon, J. Kahn, P. D. Seymour

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

37 Scopus citations

Abstract

A graph H is d-degenerate if every subgraph of it contains a vertex of degree smaller than d. For a graph G, let α_d(G) denote the maximum number of vertices of an induced d-degenerate subgraph of G. Sharp lowers bounds for α_d(G) in terms of the degree sequence of G are obtained, and the minimum number of edges of a graph G with n vertices and α₂(G) ≤ m is determined precisely for all m ≤ n.

Original language	English (US)
Pages (from-to)	203-211
Number of pages	9
Journal	Graphs and Combinatorics
Volume	3
Issue number	1
DOIs	https://doi.org/10.1007/BF01788542
State	Published - Dec 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01788542

Cite this

@article{9725c1f1997f486f816ef9d916600196,

title = "Large induced degenerate subgraphs",

abstract = "A graph H is d-degenerate if every subgraph of it contains a vertex of degree smaller than d. For a graph G, let αd(G) denote the maximum number of vertices of an induced d-degenerate subgraph of G. Sharp lowers bounds for αd(G) in terms of the degree sequence of G are obtained, and the minimum number of edges of a graph G with n vertices and α2(G) ≤ m is determined precisely for all m ≤ n.",

author = "N. Alon and J. Kahn and Seymour, \{P. D.\}",

year = "1987",

month = dec,

doi = "10.1007/BF01788542",

language = "English (US)",

volume = "3",

pages = "203--211",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Large induced degenerate subgraphs

AU - Alon, N.

AU - Kahn, J.

AU - Seymour, P. D.

PY - 1987/12

Y1 - 1987/12

N2 - A graph H is d-degenerate if every subgraph of it contains a vertex of degree smaller than d. For a graph G, let αd(G) denote the maximum number of vertices of an induced d-degenerate subgraph of G. Sharp lowers bounds for αd(G) in terms of the degree sequence of G are obtained, and the minimum number of edges of a graph G with n vertices and α2(G) ≤ m is determined precisely for all m ≤ n.

AB - A graph H is d-degenerate if every subgraph of it contains a vertex of degree smaller than d. For a graph G, let αd(G) denote the maximum number of vertices of an induced d-degenerate subgraph of G. Sharp lowers bounds for αd(G) in terms of the degree sequence of G are obtained, and the minimum number of edges of a graph G with n vertices and α2(G) ≤ m is determined precisely for all m ≤ n.

UR - https://www.scopus.com/pages/publications/0344095623

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

U2 - 10.1007/BF01788542

DO - 10.1007/BF01788542

M3 - Article

AN - SCOPUS:0344095623

SN - 0911-0119

VL - 3

SP - 203

EP - 211

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Large induced degenerate subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this