Tripartite version of the Corrádi-Hajnal theorem (Q1613547): Difference between revisions

The authors give a version for tripartite graphs of a classical theorem in extremal graph theory (for the Corrádi-Hajnal theorem see \textit{K. Corrádi} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423-439 (1963; Zbl 0118.19001)]). Namely, given a tripartite graph \(G\) such that each vertex is adjacent to at least \((2/3)N\) vertices in each of the other classes, then either \(G\) contains a subgraph that consists of \(N\) disjoint triangles or \(G\) is a specific graph characterized by the authors with the property that each vertex is adjacent to exactly \((2/3)N\) vertices in each of the other classes. The proof is based in two main tools: the regularity lemma [\textit{E. Szemerédi}, Colloq. Internat. CNRS, 399-401 (1978; Zbl 0413.05055)], and the blow-up lemma [\textit{J. Komlós, G. N. Sárközy} and \textit{E. Szemerédi}, Combinatorica 17, 109-123 (1997; Zbl 0880.05049)].