Turán numbers and anti-Ramsey numbers for short cycles in complete $3$-partite graphs

Abstract

We call a $4$-cycle in $K_{n_1,n_2,n_3}$ multipartite, denoted by $C_4^{\text{multi}}$, if it contains at least one vertex in each part of $K_{n_1,n_2,n_3}$. The Turán number $\text{ex}(K_{n_1,n_2,n_3},C_4^{\text{multi}})$ $($ respectively, $\text{ex}(K_{n_1,n_2,n_3},\{C_3,C_4^{\text{multi}}\})$ $)$ is the maximum number of edges in a graph $G\subseteq K_{n_1,n_2,n_3}$ such that $G$ contains no $C_4^{\text{multi}}$ $($ respectively, $G$ contains neither $C_3$ nor $C_4^{\text{multi}}$ $)$. We call a $C_4^{multi}$ rainbow if all four edges of it have different colors. The ant-Ramsey number $\text{ar}(K_{n_1,n_2,n_3},C_4^{\text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_1,n_2,n_3}$ with no rainbow $C_4^{\text{multi}}$. In this paper, we determine that $\text{ex}(K_{n_1,n_2,n_3},C_4^{\text{multi}})=n_1{n}_2+2n_3$ and $\text{ar}(K_{n_1,n_2,n_3},C_4^{\text{multi}})=\text{ex}(K_{n_1,n_2,n_3},\{C_3,C_4^{\text{multi}}\})+1=n_1{n}_2+n_3+1,$ where $n_1\ge n_2\ge n_3\ge 1.$

References in corpus (1)

• The anti-Ramsey number of $C_3$ and $C_4$ in the complete $r$-partite graphs

Cited by in corpus (1)

• Anti-Ramsey numbers for trees in complete multi-partite graphs