Turán number of disjoint triangles in 4-partite graphs

Jie Han, Yi Zhao

Published 2019-06-05Version 1

Let $k\ge 2$ and $n_1\ge n_2\ge n_3\ge n_4$ be integers such that $n_4$ is sufficiently larger than $k$. We determine the maximum number of edges of a 4-partite graph with parts of sizes $n_1,\dots, n_4$ that does not contain $k$ vertex-disjoint triangles. For any $r> t\ge 3$, we give a conjecture on the maximum number of edges of an $r$-partite graph that does not contain $k$ vertex-disjoint cliques $K_t$. We also determine the largest possible minimum degree among all $r$-partite triangle-free graphs.