Abstract
It is shown that any graph onn vertices containing no clique and no independent set ont + 1 vertices has at least
distinct induced subgraphs.
Similar content being viewed by others
References
Alon, N.: Ramsey graphs cannot be defined by real polynomials. J. Graph Theory, in press.
Alon, N., Bollobás, B.: Graphs with a small number of distinct induced subgraphs. Discrete Math.75, 23–30 (1989)
Erdös, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc.53, 292–294 (1947)
Erdös, P., Hajnal, A.: Ramsey type theorems. Discrete Applied Math.25, 37–52 (1989)
Erdös, P., Hajnal, A.: On the number of distinct induced subgraphs of a graph. Discrete Math.75, 145–154 (1989)
Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory. New York: Wiley Interscience 1980
Rödl, V.: Private communication
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alon, N., Hajnal, A. Ramsey graphs contain many distinct induced subgraphs. Graphs and Combinatorics 7, 1–6 (1991). https://doi.org/10.1007/BF01789457
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01789457