Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs (Q2870527)

Let \(k, r \geq 2\). We consider an edge-colored complete graph \(K_n\) on \(n\) vertices by \(r\) colors. A subgraph of \(K_n\) colored by \(r\) colors is almost spanning if it has \(n - c\) vertices where \(c\) is a constant independent of \(n\) and \(r\). \textit{B. Bollobás} and \textit{A. Gyárfás} [Discrete Math. 308, No. 9, 1722--1725 (2008; Zbl 1137.05025)] conjectured that for \(n > 4(k-1)\), every 2-colored \(K_n\) contains a \(k\)-connected monochromatic subgraph on at least \(n-2(k-1)\) vertices. \textit{L. Gerencser} and \textit{A. Gyarfas} [Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 10, 167--170 (1967; Zbl 0163.45502)] studied the largest monochromatic subgraph in an \(r\)-colored \(K_n\). Since \textit{H. Liu} et al. [J. Graph Theory 61, No. 1, 22--44 (2009; Zbl 1202.05079)] proved that the largest monochromatic \(k\)-connected subgraph in edge-colored complete graph \(K_n\) with \(r\) colors has approximately \(\frac{n}{r-1}\) vertices, in order to guarantee monochromatic almost spanning \(k\)-connected subgraph, the authors of this paper proposed adding restrictions on the coloring. Let \(G\) be a graph. A coloring of the edges of \(K_n\) is rainbow \(G\)-free if it does not contain any copy of \(F\) whose edges have pairwise different colors. Let \({\mathcal G}\) be the collection of graphs \(G\) satisfying the property that in every rainbow \(G\)-free coloring of \(K_n\) using \(r\) colors, there is a monochromatic almost spanning \(k\)-connected subgraph. Denote the path on \(n\) vertices by \(P_n\) and we obtain \(P_4^+\) from \(P_4\) by adding a vertex adjacent to an internal vertex of \(P_4\). The authors proved that the set \({\mathcal G}\) consists of \(K_3\), \(P_6\), \(P_4^+\), and their connected subgraphs having at least three vertices.