Given positive integers k and ℓ we write G → (K k , K ℓ ) if every 2-colouring of the edges of G yields a red copy of K k or a blue copy of K ℓ . We prove that for every integer k ≥ 3, there exists a graph G such that G→(K k ,K k ) while G → (K k+1 , K k-1 ). This result can be viewed as a variation of a classical theorem of Nešetřil and Rödl [11], who proved that for every k ≥ 2 there is a graph G such that K k ⊆ G and G → K k-1 . Our construction combines probabilistic methods and hypergraph container techniques to produce graphs exhibiting this Ramsey behavior.

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-colored random graph. More precisely, we show that for $p\gg n^{-1/6}{(\ln n)}^{1/6}$, in any $3$-edge coloring of the random graph $G(n,p)$ we can find three monochromatic trees such that their union covers all vertices. This improves, for three colors, a result of Bucić, Korándi, and Sudakov.