Abstract
A graphH isd-degenerate if every subgraph of it contains a vertex of degree smaller thand. For a graphG, letα d (G) denote the maximum number of vertices of an inducedd-degenerate subgraph ofG. Sharp lowers bounds forα d (G) in terms of the degree sequence ofG are obtained, and the minimum number of edges of a graphG withn vertices andα 2 (G) ≤ m is determined precisely for allm ≤ n.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Comb. Theory (A)29, 354–360 (1980)
Berge, C.: Graphes et Hypergraphes. Paris: Dunod 1970
Bollobás, B.: Extremal Graph Theory. New York-London: Academic Press 1978
Erdös, P., Spencer, J.: Probabilistic Methods in Combinatorics. New York: Academic Press 1974
Griggs, J.R.: Lower bounds on the independence number in terms of the degrees. J. Comb. Theory (B)34, 22–39 (1983)
Turán, P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok48, 436–452 (1941)
Wei, V.K.: A lower bound on the stability number of a simple graph. Bell Laboratories Technical Memorandum No. 81-11217-9(1981)
Author information
Authors and Affiliations
Additional information
Research supported in part by an Allon Fellowship and by a Bat-Sheva de Rothschild grant.
Research supported in part by NSF grant MCS 8301867, and by a Sloan Research Fellowship.
Rights and permissions
About this article
Cite this article
Alon, N., Kahn, J. & Seymour, P.D. Large induced degenerate subgraphs. Graphs and Combinatorics 3, 203–211 (1987). https://doi.org/10.1007/BF01788542
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF01788542