Multicolor Erdős--Rogers Functions

Abstract

In this paper, we study a multicolor variant of Erd\H{o}s--Rogers functions. Let $f_{\alpha_s; K_{i_1}, \cdots, K_{i_t}}(n)$ be the largest integer $m$ such that there is always an induced $K_s$-free subgraph of size $m$ in every $n$-vertex graph with a $t$-edge-coloring in which the edges with the $j$-th color induce no copy of $K_{i_j}$. We establish both upper and lower bounds for this multicolor version. Specifically, we show that $f_{\alpha_5; K_3, K_3}(n) = n^{1/2+o(1)}$, $\Omega(n^{5/11}) \le f_{\alpha_5; K_3, K_3, K_3}(n) \le n^{1/2+o(1)}$, and $\Omega(n^{20/61}) \le f_{\alpha_5; K_3, K_3, K_3, K_3}(n) \le n^{1/3+o(1)}$.

Categories