zbMATH — the first resource for mathematics

On generalized Ramsey theory: The bipartite case. (English) Zbl 1023.05101
Summary: Given graphs \(G\) and \(H\), a coloring of \(E(G)\) is called an \((H,q)\)-coloring if the edges of every copy of \(H\subseteq G\) together receive at least \(q\) colors. Let \(r(G, H,q)\) denote the minimum number of colors in an \((H,q)\)-coloring of \(G\). We determine, for fixed \(p\), the smallest \(q\) for which \(r(K_{n,n}, K_{p,p},q)\) is linear in \(n\), the smallest \(q\) for which it is quadratic in \(n\). We also determine the smallest \(q\) for which \(r(K_{n,n}, K_{p,p},q)= n^2- O(n)\), and the smallest \(q\) for which \(r(K_{n,n}, K_{p,p},q)= n^2- O(1)\). Our results include showing that \(r(K_{n,n}, K_{2,t+1},2)\) and \(r(K_n, K_{2,t+1}, 2)\) are both \((1+ o(1))\sqrt{n/t}\) as \(n\to\infty\), thereby proving a special case of a conjecture of F. R. K. Chung and R. L. Graham [J. Comb. Theory, Ser. B 18, 164-169 (1975; Zbl 0298.05122)]. Finally, we determine the exact value of \(r(K_{n,n}, K_{3,3},8)\), and prove that \(2n/3\leq r(K_{n,n}, C_4,3)\leq n+1\). Several problems remain open.

05C55 Generalized Ramsey theory
05D10 Ramsey theory
Full Text: DOI
[1] M. Ajtai, J. Komlós, and, E. Szemerédi, On a conjecture of Loebl, in, Proc, 7th International Conference on Graph Theory, Kalamazoo, MI, 1993.
[2] Alon, N.; Spencer, J., The probabilistic method, (1992), Wiley New York
[3] Alon, N.; Rónyai, L.; Szabó, T., Norm-graphs: variations and application, J. combin. theory ser. B, 76, 280-290, (1999) · Zbl 0935.05054
[4] M. Axenovich, A generalized Ramsey problem, submitted for publication. · Zbl 0969.05042
[5] Bollobás, B., Extremal graph theory, (1978), Academic Press London/New York · Zbl 0419.05031
[6] Bollobás, B., Modern graph theory, (1998), Springer-Verlag New York · Zbl 0902.05016
[7] Brown, W.G.; Erdős, P.; Sós, V.T., Some extremal problems on r-graphs, New directions in the theory of graphs, proc. 3rd ann arbor conf. on graph theory, university of michigan, 1971, (1973), Academic Press New York, p. 53-63
[8] Chung, F.R.K.; Graham, R.L., On multicolor Ramsey numbers for bipartite graphs, J. combin. theory ser. B, 18, 164-169, (1975) · Zbl 0298.05122
[9] Chung, F.R.K., Ramsey numbers in multi-colors, (1974), Univ. of Pennsylvania
[10] Brown, W.G., On graphs that do not contain a thomsen graph, Can. math. bull., 9, 281-289, (1966) · Zbl 0178.27302
[11] Chvátal, V., On finite polarized partition relations, Can. math. bull., 12, 321-326, (1969) · Zbl 0186.01702
[12] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-509, (1952) · Zbl 0048.11804
[13] D. Eichhorn, personal communication.
[14] Erdős, P., Solved and unsolved problems in combinatorics and combinatorial number theory, Congr. numer., 32, 49-62, (1981)
[15] Erdős, P.; Gyárfás, A., A variant of the classical Ramsey problem, Combinatorica, 17, 459-467, (1997) · Zbl 0910.05034
[16] Erdős, P.; Rado, R., A partition calculus in set theory, Bull. am. math. soc., 62, 427-489, (1956) · Zbl 0071.05105
[17] Erdős, P.; Rényi, A.; Sós, V.T., On a problem of graph theory, Studia sci. math. hungar., 1, 215-235, (1966) · Zbl 0144.23302
[18] Füredi, Z., New asymptotics for bipartite Turán numbers, J. combin. theory ser. A, 75, 141-144, (1996) · Zbl 0858.05064
[19] Füredi, Z., Un upper bound on zarankiewicz’ problem, Combin. probab. comput., 5, 29-33, (1996) · Zbl 0857.05048
[20] Griggs, J.R.; Simonovits, M.; Thomas, G.R., Extremal graphs with bounded densities of small graphs, J. graph theory, 29, 185-207, (1998) · Zbl 0919.05031
[21] Huxley, M.N.; Iwaniec, H., Bombieri’s theorem in short intervals, Mathematika, 22, 188-194, (1975) · Zbl 0317.10048
[22] Kővári, T.; Sós, V.T.; Turán, P., On a problem of K. zarankiewicz, Colloq. math., 3, 50-57, (1954) · Zbl 0055.00704
[23] Mubayi, D., Edge-coloring cliques with three colors on all 4-cliques, Combinatorica, 18, 293-296, (1998) · Zbl 0910.05035
[24] Parsons, T.D., Ramsey graphs and block designs, J. combin. theory ser. A, 20, 12-19, (1976) · Zbl 0324.05014
[25] Pippenger, N.; Spencer, J., Asymptotic behavior of the chromatic index for hypergraphs, J. combin. theory ser. A, 51, 24-42, (1989) · Zbl 0729.05038
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.