Forbidden rainbow subgraphs that force large monochromatic or multicolored k-connected subgraphs

Let $n,k,m$ be positive integers with $n\gg m\gg k$, and let $\mathcal{A}$ be the set of graphs $G$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $n-f(G,k,m)$ in any rainbow $G$-free coloring of $K_n$ using all the $m$ colors. In this paper, we prove that the set $\mathcal{A}$ consists of precisely $P_6$, $P_3\cup P_4$, $K_2\cup P_5$, $K_2\cup 2P_3$, $2K_2\cup K_3$, $2K_2\cup P_4^{+}$, $3K_2\cup K_{1,3}$ and their subgraphs of order at least 3. Moreover, we show that for any graph $H\in $\mathcal{A}$$,if$n$sufficientlylargerthan$m$and$k$,thenanyrainbow$(P_3\cup H)$-freecoloringof$K_n$usingallthe$m$colorscontainsa$k$-connectedmonochromaticsubgraphoforderatleast$cn$,where$c=c(H)$ is a constant, not depending on $n$, $m$ or $k$. Furthermore, we consider a parallel problem in complete bipartite graphs. Let $s,t,k,m$ be positive integers with $\mathrm{m}\mathrm{i}\mathrm{n}\{s,t\}\gg m\gg k$ and $m\ge \mathrm{\mid }E(H)\mathrm{\mid }$, and let $\mathcal{B}$ be the set of bipartite graphs $H$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $s+t-f(H,k,m)$ in any rainbow $H$-free coloring of $K_{s,t}$ using all the $m$ colors, where $f(H,k,m)$ is not depending on $s$ or $t$. We prove that the set $\mathcal{B}$ consists of precisely $2P_3$, $2K_2\cup K_{1,3}$ and their subgraphs of order at least 3. Finally, we consider the large $k$-connected multicolored subgraph instead of monochromatic subgraph. We show that for $1\le k\le 3$ and $n$ sufficiently large, every Gallai-3-coloring of $K_n$ contains a $k$-connected subgraph of order at least $n-\lfloor \frac{k-1}{2}\rfloor$ using at most two colors. We also show that the above statement is false for $k=4t$, where $t$ is an positive integer.