Turán-Ramsey problems. (English) Zbl 0857.05050
Given graphs \(F_1,\dots, F_k\), write \(\text{ex}_k(n;F_1,\dots,F_k)\) for the maximal size of a graph \(G\) of order \(n\) whose edges can be coloured with \(k\) colours such that \(G\) contains no \(F_i\) all of whose edges are coloured with the \(i\)th colour. Alternatively, \(\text{ex}_k(n; F_1,\dots,F_k)\) is the maximal size of \(G_1\cup\cdots\cup G_k\), where \(G_1,\dots, G_k\) are graphs on the same set of \(n\) vertices, and no \(G_i\) contains \(F_i\) as a subgraph. This note proves the asymptotic bound for this function, and discusses related problems.
Reviewer: C.Jagger (Cambridge)
References:
| [1] | Bollobás, B., Graph Theory — An Introductory Course, (Graduate Texts in Mathematics, Vol. 63 (1979), Springer: Springer New York), x+180 · Zbl 0688.05016 |
| [2] | Bollobás, B.; Erdős, P., On the structure of edge graphs, Bull. London Math. Soc., 5, 317-321 (1973) · Zbl 0277.05135 |
| [3] | Bollobás, B.; Erdős, P., On a Ramsey-Turán type problem, J. Combin. Theory, Ser. B, 21, 166-168 (1976) · Zbl 0337.05134 |
| [4] | Bollobás, B.; Erdős, P.; Simonovits, M., On the structure of edge graphs II, J. London Math. Soc., 12, 219-224 (1976) · Zbl 0318.05110 |
| [5] | Chvátal, V.; Szemerédi, E., On the Erdős-Stone theorem, J. London Math. Soc., 23, 207-214 (1981) · Zbl 0485.05034 |
| [6] | Erdős, P.; Hajnal, A.; Simonovits, M.; Sós, V. T.; Szemerédi, E., Turán-Ramsey type theorems and simple asymptotically extremal structures, Combinatorica, 13, 31-56 (1993) · Zbl 0774.05050 |
| [7] | Erdős, P.; Hajnal, A.; Sós, V. T.; Szemerédi, E., More results on Ramsey-Turán type problems, Combinatorica, 3, 69-81 (1983) · Zbl 0526.05031 |
| [8] | Erdős, P.; Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hungar., 1, 51-57 (1966) · Zbl 0178.27301 |
| [9] | Erdős, P.; Sós, V. T., Some remarks on Ramsey’s and Turán’s theorem, Coll. Math. Soc. J. Bolyai, Combinatorial Theory, 395-404 (1969), Balatonfüred · Zbl 0209.28002 |
| [10] | Erdős, P.; Stone, A. H., On the structure of edge graphs, Bull. Amer. Math. Soc., 52, 1087-1091 (1946) · Zbl 0063.01277 |
| [11] | Sós, V. T., On extremal problems in graph theory, (Guy, R.; Hanani, H.; Sauer, N.; Schonheim, J., Combinatorial Structures and their Applications, Proc. Calgary Internat. Conf (1970), Gordon and Breach: Gordon and Breach New York), 407-410 · Zbl 0253.05145 |
| [12] | Szemerédi, E., Teljes négyes gráfokat nem tartalmazó gráfokról (On graphs containing no complete subgraphs with four vertices, Mat. Lapok, 23, 111-116 (1972), (in Hungarian) |
| [13] | Turán, P., Egy gráfelméleti szélsöértékfeladatról, Math. Fizikai Lapok, 48, 436-452 (1941), (in Hungarian) · JFM 67.0732.03 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
