Multicolor Erdős--Rogers Functions

Abstract

In this paper, we study a multicolor variant of Erdős--Rogers functions. Let $f_{\hat{I}{\pm }_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_{\hat{I}{\pm }_5;K_3,K_3}(n)=n^{1/2+o(1)}$, $\hat{I}\text{c◯}(n^{5/11})\le f_{\hat{I}{\pm }_5;K_3,K_3,K_3}(n)\le n^{1/2+o(1)}$, and $\hat{I}\text{c◯}(n^{20/61})\le f_{\hat{I}{\pm }_5;K_3,K_3,K_3,K_3}(n)\le n^{1/3+o(1)}$.

17 pages, comments are welcome