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

Let n,k,m be positive integers with n≫m≫k, and let G (respectively, H) be the set of connected (respectively, disconnected) graphs G such that there is a k-connected monochromatic subgraph of order at least n−f(G,k,m) in every rainbow G-free m-coloring of K_n, where f(G,k,m) does not depend on n. The set G was determined by Fujita and Magnant in a previous paper. In this paper, we give a complete characterization of H, and we show that G∪H consists of precisely P₆, P₃∪P₄, K₂∪P₅, K₂∪2P₃, 2K₂∪K₃, 2K₂∪P₄⁺, 3K₂∪K_1,3 and their subgraphs. We also consider a parallel problem for complete bipartite graphs. Let s,t,k,m be positive integers with mins,t≫m≫k and m≥|E(H)|, and let B be the set of bipartite graphs H such that there is a k-connected monochromatic subgraph of order at least s+t−f(H,k,m) in any rainbow H-free m-coloring of K_s,t, where f(H,k,m) does not depend on s or t. We prove that the set B consists of precisely 2P₃, 2K₂∪K_1,3 and their subgraphs. Finally, we consider large k-connected multicolored subgraphs instead of monochromatic subgraphs. We show that for 1≤k≤3 and sufficiently large n, every Gallai-3-coloring of K_n contains a k-connected subgraph of order at least n−[Formula presented] using at most two colors. For any positive integer t, we also show that the above statement is false for k=4t.