Bipartite rainbow Ramsey numbers. (Q1426110): Difference between revisions

This article introduces, proves the existence of, and computes some values of a new Ramsey number. Given a graph \(G\), with a subgraph \(H\), call an edge-coloring of \(G\) {rainbow} on \(H\) if the coloring assigns every edge of \(H\) its own color. Write \(G \to \langle G_1, G_2 \rangle\) if, for every coloring of \(G\), the coloring is either monochromatic on \(G_1\) or rainbow on \(G_2\). Then the {bipartite rainbow Ramsey number} of bipartite graphs \(G_1\) and \(G_2\) is the least number \(N = \text{BRR}(G_1, G_2)\) such that \(K_{N,N} \to \langle G_1, G_2 \rangle\). The primary result of this paper is that BRR\((G_1, G_2)\) exists if and only if \(G_1\) is a star or \(G_2\) is a star forest. (The proof of this has a minor glitch, but works if \(G_2\) is a star forest of \(m\) edges.) Most of the paper is devoted to computations of bipartite rainbow Ramsey numbers. Most notably, \[ \text{BRR}(K_{1,n}, K_{1,m}) = \text{BRR}(nK_2, mK_2) =\text{BRR}(K_{1,n}, mK_2) =(n-1)(m-1)+1, \] but if \(n \geq 2\) and \(m \geq 3\), \[ \max \{ 2(n-1)(m-2)+1, (n-1)(m-1)+1\} \leq \text{BRR}(nK_2, K_{1,m}) \leq (3m-5)(n-1) + 1. \] And if \(2 \leq n, m\) and \(m \leq 2n - 3\), and if \(P_{m+1}\) is the path of \(m\) edges, then BRR\((K_{1,n}, P_{m+1}) =(n-1)(m-1)+1\).