Large induced degenerate subgraphs

Research output: Contribution to journalArticlepeer-review

36 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 α2(G) ≤ m is determined precisely for all m ≤ n.

Original languageEnglish (US)
Pages (from-to)203-211
Number of pages9
JournalGraphs and Combinatorics
Volume3
Issue number1
DOIs
StatePublished - Dec 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Large induced degenerate subgraphs'. Together they form a unique fingerprint.

Cite this