×

Turán-Ramsey theorems and \(K_p\)-independence numbers. (English) Zbl 0812.05031

The \(K_p\)-independence number \(\alpha_p(G)\) of a graph \(G\) is the maximum order of an induced subgraph of \(G\) that contains no \(K_p\). In this paper, the authors study the following problem: For integers \(r\), \(p\), \(m>0\) and graphs \(L_1,\dots, L_r\), what is the maximum number of edges in a graph \(G\) of order \(n\) such that \(\alpha_p(G)\leq m\) and there is an edge-colouring of \(G\) with \(r\) colours such that the \(j\)th colour class contains no copy of \(L_j\), for \(j= 1,\dots, r\) (this maximum number is denoted by \(\text{RT}_p(n, L_1,\dots, L_r, m)\))? They obtain several results for graphs \(G\) of order \(n\) with small \(K_p\)-independence number \(\alpha_p(G)\). Some structure theorems are given for the case \(\alpha_p(G_n)= o(n)\), showing that there are graphs with fairly simple structure that are within \(o(n^2)\) of the extremal size; the structure is described in terms of the edge densities between certain sets of vertices. They also study the problem of determining the asymptotic value of \[ \theta_p(K_q)= \lim_{n\to \infty} {\text{RT}_p(n, K_q, o(n))\over\binom{n}{2}} \] for \(p< q\). They list several open problems and make some conjectures in the paper.

MSC:

05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Katona, Annals of Discrete Math. 28 pp 159– (1985)
[2] DOI: 10.1112/plms/s2-30.1.264 · JFM 55.0032.04
[3] DOI: 10.1007/BF02189089 · Zbl 0658.05041
[4] Erd?s, Canad. Journal of Math. 13 pp 346– (1961) · Zbl 0097.39102
[5] Zykov, Mat Sbornik 24 pp 163– (1949)
[6] Erd?s, Theory of Graphs pp 77– (1968)
[7] Turán, Collected papers of Paul Turán 1?3 (1989)
[8] DOI: 10.2307/2000222 · Zbl 0607.05040
[9] Turán, Proc. Naval Research Laboratory pp 137– (1970)
[10] Brown, Colloq. Math. Soc. J. Bolyai 37 pp 119– (1985)
[11] Turán, Proc. Internat. Conference in Varna, Bulgaria, 1970 (1972)
[12] Brown, Problèmes Combinatoires et Thèorie des Graphes pp 63– (1978)
[13] DOI: 10.1016/0095-8956(73)90034-8 · Zbl 0253.05124
[14] Turán, Colloq. Math. 3 pp 19– (1954)
[15] DOI: 10.1016/0095-8956(76)90057-5 · Zbl 0337.05134
[16] Turán, Matematikai Lapok 48 pp 436– (1941)
[17] Bollobás, Extremal graph theory (1978)
[18] Szemerédi, Problèmes Combinatoires et Théorie des Graphes pp 399– (1978)
[19] Bollobás, Elemente der Math. 44 pp 121– (1989)
[20] Szemerédi, Mat. Lapok 23 pp 111– (1972)
[21] Erd?s, Bull. Amer. Math. Soc. 52 pp 1089– (1946)
[22] Erd?s, Coll. Soc. J. Bolyai 4 pp 395– (1969)
[23] Erd?s, Studia Sci. Math. Hungar. 1 pp 51– (1966)
[24] Erd?s, Canadian Journal of Math pp 702– (1962)
[25] Erd?s, Canadian Math. Bulletin 15 pp 27– (1972) · Zbl 0232.05003
[26] Erd?s, Studies in Pure Mathematics (presented to R. Rado) pp 89– (1971)
[27] DOI: 10.1016/0012-365X(72)90004-0 · Zbl 0236.05119
[28] DOI: 10.1007/BF01202788 · Zbl 0774.05050
[29] DOI: 10.1007/BF02579342 · Zbl 0526.05031
[30] DOI: 10.1007/BF02020444 · Zbl 0151.33701
[31] Simonovits, Selected Topics in Graph Theory pp 161– (1983)
[32] Simonovits, Theory of Graphs pp 279– (1968)
[33] DOI: 10.1007/BF02124681 · Zbl 0732.05031
[34] Graham, Ramsey Theory (1980)
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.