How many colors do we need to avoid bichromatic triangles?

Question

Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors. I wonder if the following type of question has been studied before, where monochromatic is replaced by bichromatic (which now I use in the sense of having at most two colors).

How many colors do we need to color the edges of a given graph to avoid a certain bichromatic subgraph?

We could define the multicolor biRamsey number of $G$, denoted by $biR_k(G)$, as the least integer $n$ such that in any $k$-coloring of $K_n$ there is a bichromatic copy of $G$. Probably the simplest example is $biR_3(K_3)=5$, as a coloring of a complete graph has no bichromatic triangle if and only if every monochromatic component is a matching, and such a $3$-coloring exists for $K_n$ if and only if $n\le 4.$

Obviously, we have $biR_k(G)\le R_k(G)$, but I don't see any general lower bound for $biR_k$. Has this parameter ever been studied? (Possibly under a less brilliant name.)

Motivation: I would need something like in any $n$-coloring of a graph on $n$ vertices and $\Omega(n^2)$ edges there is a trichromatic $K_{3,3}$, or something similar, where I have other conditions, like every color class is a matching.

Update: As you can see from the answers of Ilya and Jan, the answer to the motivation is negative, but I can produce other similar conditions, so I am still interested whether the problem has been studied.

Answer 1

Problems of this variety have been studied, beginning with a paper of Erdős and Gyárfás, 'A variant of the classical Ramsey problem'. In that paper, they define a function $f(n,p,q)$ to be the smallest number of colours $k$ needed to produce a $k$-colouring of the edges of $K_n$ such that every $K_p$ contains at least $q$ distinct colours. The study of this function and its variants (such as replacing $K_p$ with a general graph $H$) leads to a great number of interesting questions. For example, even the behaviour of $f(n,4,3)$ is poorly understood.

Answer 2

Regarding the question in "Motivation": a $1$-factorization of $K_{n,n}$ is essentially an $n\times n$ Latin square, and a $3$-chromatic $K_{3,3}$ would be a proper Latin subsqare.

This paper shows that there are Latin $n\times n$ squares with no proper Latin subsquares for $n=pq \neq 6$ where $p,q$ are distinct primes. The author claims that for $n$ prime it is well known that the multiplication table of the group of order $p$ is a Latin square with no proper Latin subsquares. Indeed, a proper Latin subsquare would correspond to a nontrivial proper subgroup.

Constructions of Latin $n\times n$ squares with no proper Latin subsquares are known for all odd $n$: http://www.sciencedirect.com/science/article/pii/S0195669805000909

Answer 3

As for $triR_k(K_{3,3})$, I would assume that the usual `averaging' approach should give an estimate not far from the optimal one. Take three colors with the maximal number of edges in them and estimate the number of triples of vertices having a common neighbour by these colors. If this number exceeds $2{n\choose 3}$, we are done. [EDIT] This seems to be covered by the Kővári–Sós–Turán theorem, see https://en.wikipedia.org/wiki/Zarankiewicz_problem. [END EDIT]

Exactly on the described situation, it seems that you have no chance for finding $K_{3,3}$ even in a complete graph with $n$ vertices and $n$-colored edges. Indeed, if we take a regular $(6k+1)$-gon and paint all parallel edges in one color, then the resulting graph would not contain a trichromatic $K_{3,3}$. Moreover, it seems that here we have some regularity which helps finding such $K_{3,3}$...