Abstract
It is shown that for arbitrary positiveε there exists a graph withoutK 4 and so that all its subgraphs containing more than 1/2 +ε portion of its edges contain a triangle (Theorem 2). This solves a problem of Erdös and Nešetřil. On the other hand it is proved that such graphs have necessarily low edge density (Theorem 4).
Theorem 3 which is needed for the proof of Theorem 2 is an analog of Goodman's theorem [8], it shows that random graphs behave in some respect as sparse complete graphs.
Theorem 5 shows the existence of a graph on less than 1012 vertices, withoutK 4 and which is edge-Ramsey for triangles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N.: Personal communication
Bollobás, B.: Extermal Graph Theory. London-New York-San Francisco: Academic Press 1978
Chernoff, H.: A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Ann. Stat.23, 493–502 (1952)
Erdös, P.: Problems and results on finite and infinite graphs. In: Recent Advances in Graph Theory (Proceedings of the Symposium held in Prague 1974) edited by M. Fiedler, pp 183–192. Praha: Academia 1974
Erdös, P.: On some of my conjectures in number theory and combinatorics. Congr. Numerantium39, 3–19 (1983)
Erdös, P., Spencer, J.: Probabilistic Methods in Combinatorics. Budapest: Akadémiai Kiado 1974
Folkman, J.: Graphs with monochromatic complete subgraphs in every edge colouring. SIAM J. Appl. Math.18, 19–29 (1970)
Goodman, A.W.: On sets of acquaintances and strangers at any party. Amer. Math. Mon.66, 778–783 (1959)
Graham, R.L.: On edgewise 2-coloured graphs with monochromatic triangles and containing no complete hexagon. J. Comb. Theory4, 300 (1968)
Graham, R.L.: Rudiments of Ramsey theory. Reg. Conf. Ser. Math.45 (1981)
Irving, R.W.: On a bound of Graham and Spencer for a graph colouring constant. J. Comb. Theory (B)15, 200–203 (1973)
Nešetřil, J., Rödl, V.: The Ramsey property for graphs with forbidden complete subgraphs. J. Comb. Theory (B)20, 243–249 (1976)
Nešetřil, J., Rödl, V.: Partition theory and its applications. Lond. Math. Soc. Lect. Note Ser.38, 96–157 (1979)
Rödl, V.: On universality of graphs with uniformly distributed edges. Discrete Math. (to appear)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Frankl, P., Rödl, V. Large triangle-free subgraphs in graphs withoutK 4 . Graphs and Combinatorics 2, 135–144 (1986). https://doi.org/10.1007/BF01788087
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF01788087