Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T11:59:54.105Z Has data issue: false hasContentIssue false
  • English
  • Français

Ks-Free Graphs Without Large Kr-Free Subgraphs

Published online by Cambridge University Press:  12 September 2008

Michael Krivelevich
Michael Krivelevich
Affiliation:
Department of Mathematics, Technion – Israel Institute of Technology, Haifa 32000, Israel e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The main result of this paper is that for every 2 ≤ r < s, and n sufficiently large, there exist graphs of order n, not containing a complete graph on s vertices, in which every relatively not too small subset of vertices spans a complete graph on r vertices. Our results improve on previous results of Bollobás and Hind.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 3 , September 1994 , pp. 349 - 354
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ajtai, M., Erdős, P., Komlós, J. and Szemerédi, A. (1981) On Turán's theorem for sparse graphs. Combinatorica 1 313–317.CrossRefGoogle Scholar
[2]Alon, N., Spencer, J. and Erdős, P. (1992) The probabilistic method, John Wiley & Sons.Google Scholar
[3]Bollobás, B. and Hind, H. R. (1991) Graphs without large triangle free subgraphs. Discrete Math. 87 119–131.CrossRefGoogle Scholar
[4]Erdős, P. and Gallai, T. (1961) On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hungar. Acad. Sci. 6 181–203.Google Scholar
[5]Erdős, P., Hajnal, A. and Tuza, Z. (1991) Local constraints ensuring small representing sets. J. Combin. Theory, Ser. A 58 78–84.CrossRefGoogle Scholar
[6]Erdős, P. and Lovász, L. (1975) Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A. et al. (eds.) Infinite and finite sets, North-Holland 609–628.Google Scholar
[7]Erdős, P. and Rogers, C. A. (1962) The construction of certain graphs. Canad. J. Math. 14 702–707.CrossRefGoogle Scholar
[8]Janson, S., Luczak, T. and Ruciński, A. (1990) An exponential bound for the probability of non-existence of a specified graph in a random graph. In: Kazoński, M. et al. (eds.) Random Graphs '87, John Wiley & Sons 73–87.Google Scholar
[9]Linial, N. and Rabinovich, Yu. (1994) Local and global clique numbers. J. Combin. Theory, Ser. B. 61 5–15.CrossRefGoogle Scholar
[10]Tuza, Z. (1989) Minimum number of elements representing a set system of given rank. J. Combin. Theory, Ser. A 52 84–89.CrossRefGoogle Scholar