Complete subgraphs of \(r\)-partite graphs. (English) Zbl 0793.05088
Summary: The smallest minimal degree of an \(r\)-partite graph that guarantees the existence of a complete subgraph of order \(r\) has been found for the case \(r=3\) by B. Bollobás, P. Erdős and E. Szemerédi [Discrete Math. 13, 97-107 (1975; Zbl 0306.05121)], who also gave bounds for the case \(r\geq 4\). In this paper the exact value is established for the cases \(r=4\) and 5, and the bounds for \(r\geq 6\) are improved.
MSC:
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 0306.05121References:
| [1] | Turán, Mat. Fiz. Lapok 48 pp 436– (1941) |
| [2] | Bollobás, Extremal Graph Theory pp 488– (1978) |
| [3] | Bollobás, Utilitas Math 6 pp 343– (1974) |
| [4] | DOI: 10.1016/0012-365X(75)90011-4 · Zbl 0306.05121 · doi:10.1016/0012-365X(75)90011-4 |
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.
