Tripartite Version of the Corrádi-Hajnal Theorem

Abstract

Let $G$ be a tripartite graph with $N$ vertices in each vertex class. If 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$ vertex-disjoint triangles or $G$ is a specific graph in which each vertex is adjacent to exactly $(2/3)N$ vertices in each of the other classes.

22 pages, 4 figures

Cited by in corpus (4)

• Minimum degree thresholds for bipartite graph tiling
• On the strong chromatic number of graphs
• Powers of Hamiltonian cycles in multipartite graphs
• An asymptotic multipartite Kühn-Osthus theorem