Homogeneous Set in Multigraph with Forbidden Coloring

The Erdos–Hajnal conjecture predicts that forbidding any fixed induced subgraph H in a graph on n vertices forces a clique or independent set of size at least n^ε for some ε > 0. Extending to edge-colorings, one asks whether forbidding a fixed coloring of K_k in an s-edge coloring of K_n guarantees a large homogeneous set using at most s - 1 colors. A "mixed rainbow triangle" (MRT) is a triangle where two fixed edges have distinct colors, and any edge between the third pair of vertices forms a rainbow triangle. An edge-coloring is MRT-free if it contains no such configuration. We characterize all r-colorings of μK_n that avoid MRT and, using Erdos–Ko–Rado–type results, prove that any MRT-free r-coloring of μK_n contains a homogeneous set of size Ω(n^{(r-μ-1)/(r-μ+1)} log n) using at most r - 1 colors. We also obtain large monochromatic stars and spanning trees.