Let $n, k, m$ be positive integers with $ngg mgg 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_3cup P_4$, $K_2cup P_5$, $K_2cup 2P_3$, $2K_2cup K_3$, $2K_2cup P^{+}_4$, $3K_2cup K_{1,3}$ and their subgraphs of order at least 3. Moreover, we show that for any graph $Hin mathcal{A}$, if $n$ sufficiently larger than $m$ and $k$, then any rainbow $(P_3cup H)$-free coloring of $K_n$ using all the $m$ colors contains a $k$-connected monochromatic subgraph of order at least $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 ${rm min}left{s, tright}gg mgg k$ and $mgeq |E(H)|$, 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_2cup 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 $1leq k leq 3$ and $n$ sufficiently large, every Gallai-3-coloring of $K_n$ contains a $k$-connected subgraph of order at least $n-leftlfloorfrac{k-1}{2}rightrfloor$ using at most two colors. We also show that the above statement is false for $k=4t$, where $t$ is an positive integer.
Download