Skip to main content
added update
Source Link
domotorp
  • 18.7k
  • 3
  • 57
  • 125

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.

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.

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.

Source Link
domotorp
  • 18.7k
  • 3
  • 57
  • 125

How many colors do we need to avoid bichromatic triangles?

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.