Abstract
Bollobás, Erdös, Simonovits, and Szemerédi conjectured [1] that for each positive constantc there exists a constantg(c) such that ifG is any graph which cannot be made 3-chromatic by the omission ofcn 2 edges, thenG contains a 4-chromatic subgraph with at mostg(c) vertices. Here we establish the following generalization which was suggested by Erdös [2]: For each positive constantc and positive integerk there exist positive integersf k(c) andn o such that ifG is any graph with more thann o vertices having the property that the chromatic number ofG cannot be made less thank by the omission of at mostcn 2 edges, thenG contains ak-chromatic subgraph with at mostf k(c) vertices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bollobás, B., Erdös, P., Simonovits, M., Szemerédi, E.: Extremal graphs without large forbidden subgraphs. In: Advances in Graph Theory (Cambridge Comb. Conf. Trinity College, 1977). Ann. Discrete Math.3, 29–41 (1978)
Erdös, P.: Problems and results of graphs and hypergraphs: similarities and differences. In: Recent Progress in Ramsey Theory, edited by Nešetřil, J., Rödl, V. (Proc. Third Czechoslovak Symposium on Graph Theory, Prague 1982)
Szemerédi, E.: Regular partitions of graphs. Proc. Colloq. Int. C.N.R.S., pp. 399–401 (1976)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rödl, V., Duke, R.A. On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics 1, 91–96 (1985). https://doi.org/10.1007/BF02582932
Issue Date:
DOI: https://doi.org/10.1007/BF02582932