×

Bipartite rainbow Ramsey numbers. (English) Zbl 1036.05032

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\).

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke, L. W.; Schwenk, A. J., On a bipartite form of the Ramsey problem, Proceedings of the Fifth British Combinatories Conference, Congr. Numer., XV, 17-22 (1975)
[2] Bialostocki, A.; Voxman, W., Generalizations of some Ramsey-type theorems for matchings, Discrete Math., 239, 101-107 (2001) · Zbl 0988.05063
[3] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman and Hall: Chapman and Hall New York · Zbl 0890.05001
[4] Chung, F. R.K.; Graham, R. L., On multicolor Ramsey numbers for complete bipartite graphs, J. Combin. Theory Ser. B, 18, 164-169 (1975) · Zbl 0298.05122
[5] Chvátal, V.; Harary, F., Generalized ramsey theory for graphs, III. Small off-diagonal numbers, Pacific J. Math, 41, 335-345 (1972) · Zbl 0227.05115
[6] Colbourn, C. J.; Dinitz, J. H., The CRC Handbook of Combinatorial Designs (1996), CRC Press: CRC Press New York · Zbl 0836.00010
[7] Erdös, P.; Graham, R. L., Old and new problems and results in combinatorial number theoryvan der Waerden’s theorem and related topics, Enseign. Math., 25, 2, 325-344 (1979) · Zbl 0434.10002
[8] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · JFM 61.0651.04
[9] L. Eroh, Rainbow Ramsey numbers, Ph.D. Thesis, Western Michigan University, 2000.; L. Eroh, Rainbow Ramsey numbers, Ph.D. Thesis, Western Michigan University, 2000. · Zbl 1043.05083
[10] Faudree, R. J.; Schelp, R. H., Path-path Ramsey type numbers for the complete bipartite graph, J. Combin. Theory Ser. B, 19, 161-173 (1975) · Zbl 0305.05108
[11] Goddard, W.; Henning, M. A.; Oellermann, O. R., Zarankiewicz numbers and bounds on bipartite ramsey numbers, Discrete Math., 219, 85-95 (2000) · Zbl 0953.05051
[12] Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1990), Wiley-Interscience: Wiley-Interscience New York
[13] Gyárfás, A.; Lehel, J., A Ramsey-type problem in directed and bipartite graphs, Period. Math. Hungar., 3, 299-304 (1973) · Zbl 0267.05115
[14] Gyárfás, A.; Lehel, J.; Nesetril, J.; Rödl, V.; Schelp, R. H.; Tuza, Zs., Local k-colorings of graphs and hypergraphs, J. Combin. Theory Ser. B, 43, 127-139 (1987) · Zbl 0632.05041
[15] Hatting, J. H.; Henning, M. A., Bipartite Ramsey theory, Utilitas Math., 53, 217-230 (1998) · Zbl 0908.05064
[16] Hatting, J. H.; Henning, M. A., Star-path bipartite Ramsey number, Discrete Math., 185, 255-258 (1998) · Zbl 0955.05072
[17] Henning, M. A.; Oellermann, O. R., Bipartite ramsey theorems for multiple copies of \(K_{2,2}\), Utilitas Math., 54, 13-23 (1998) · Zbl 0918.05075
[18] Irving, R. W., A bipartite Ramsey problem and Zarankiewicz numbers, Glasgow Math. J., 19, 13-26 (1978) · Zbl 0367.05051
[19] Ramsey, F., On a problem of formal logic, Proc. London Math. Soc., 30, 264-286 (1930) · JFM 55.0032.04
[20] Zarankiewicz, K., Problem P101, Colloq. Math., 2, 301 (1951)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.