Generalized and geometric Ramsey numbers for cycles. (English) Zbl 1048.05063
The authors study the Ramsey number for two cycles \(C_k, C_l\), first in the context of graphs, then for noncrossing cycles in geometric graphs. The exact value of the graph Ramsey number \(R(C_k, C_n)\) was already previously determined in several papers: R. J. Faudree and R. H. Schelp [Discrete Math. 8, 313–329 (1974; Zbl 0294.05122)], V. Rosta [J. Comb. Theory, Ser. B 15, 94–104 (1973; Zbl 0261.05118), J. Comb. Theory, Ser. B 15, 105–120 (1973; Zbl 0261.05119)], G. Chantrand and S. Schuster [Trans. Am. Math. Soc. 173, 353–362 (1972; Zbl 0255.05110)] and J. A. Bondy and P. Erdős [J. Comb. Theory, Ser. B 14, 46–54 (1973; Zbl 0248.05127)]. The present authors give another proof for the surprisingly complicated formula. Then they consider geometric graphs, that is, straight-line drawings in the plane, where the same question can be asked with the additional condition that the cycles should be noncrossing. They define \(R_g(C_k, C_l)\) as the smallest number \(n\) such that any two-coloring of the edges of any straight-line drawing of \(K_n\) contains either a crossingfree \(C_k\) in the first color or a crossingfree \(C_l\) in the second color. They show that \(kl -k -l +2\leq R_g(C_k, C_l)\leq 2kl -3k -3l +6\), and conjecture the lower bound to be the correct value.
Reviewer: Peter Braß (New York)
MSC:
| 05C55 | Generalized Ramsey theory |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 52C99 | Discrete geometry |
References:
| [1] | Bondy, J. A., Large cycles in graphs, Discrete Math., 1, 121-132 (1971) · Zbl 0224.05120 |
| [2] | Bondy, J. A.; Erdős, P., Ramsey numbers for cycles in graphs, J. Combin. Theory B, 14, 46-54 (1973) · Zbl 0248.05127 |
| [3] | S.A. Burr, Generalized Ramsey theory for graphs – a survey, in: R. Bari, F. Harary (Eds.), Graphs and Combinatorics Lecture Notes in Mathematics, Springer, Berlin, vol. 406, 1974,, pp. 52-75.; S.A. Burr, Generalized Ramsey theory for graphs – a survey, in: R. Bari, F. Harary (Eds.), Graphs and Combinatorics Lecture Notes in Mathematics, Springer, Berlin, vol. 406, 1974,, pp. 52-75. · Zbl 0293.05122 |
| [4] | Chartrand, G.; Schuster, S., On a variation of the Ramsey number, Trans. Amer. Math. Soc., 173, 353-362 (1972) · Zbl 0255.05110 |
| [5] | Chvátal, V., Tree – complete graph Ramsey numbers, J. Graph Theory, 1, 93 (1977) · Zbl 0351.05120 |
| [6] | Dilworth, R. P., A decomposition theorem for partially ordered sets, Ann. Math., 51, 161-166 (1950) · Zbl 0038.02003 |
| [7] | Erdős, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292-294 (1947) · Zbl 0032.19203 |
| [8] | Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta. Math. Acad. Sci. Hungar., 10, 337-356 (1959) · Zbl 0090.39401 |
| [9] | Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Comput. Math., 2, 53-62 (1935) |
| [10] | Faudree, R. J.; Schelp, R. H., All Ramsey numbers for cycles in graphs, Discrete Math., 8, 313-329 (1974) · Zbl 0294.05122 |
| [11] | Faudree, R. J.; Simonovits, M., Ramsey problems and their connections to Turán-type extremal problems, J. Graph Theory, 16, 25-50 (1992) · Zbl 0770.05075 |
| [12] | Gerencsér, L.; Gyárfás, A., On Ramsey-type problems, Ann. Univ. Sci. R. Eötvös Sect. Math., X, 167-170 (1967) · Zbl 0163.45502 |
| [13] | Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1990), Wiley: Wiley New York · Zbl 0705.05061 |
| [14] | Gritzmann, P.; Mohar, B.; Pach, J.; Pollack, R., Embedding a planar triangulation with vertices at specified points (solution to problem E3341), Amer. Math. Monthly, 98, 165-166 (1991) |
| [15] | Harborth, H.; Lefmann, H., Coloring arca of convex sets, Discrete Math., 220, 107-117 (2000) · Zbl 0953.05052 |
| [16] | Gy. Károlyi, J. Pach, G. Tóth, Ramsey-type results for geometric graphs. I, Proc. 12th Annual ACM Symp. on Computational Geometry, Philadelphia, 1996, pp. 359-365; Discrete Comput. Geom. 18 (1997) 247-255.; Gy. Károlyi, J. Pach, G. Tóth, Ramsey-type results for geometric graphs. I, Proc. 12th Annual ACM Symp. on Computational Geometry, Philadelphia, 1996, pp. 359-365; Discrete Comput. Geom. 18 (1997) 247-255. · Zbl 0940.05046 |
| [17] | Gy. Károlyi, J. Pach, G. Tóth, P. Valtr, Ramsey-type results for geometric graphs. II, Proc. 13th Annu. ACM Symp. on Computational Geometry, Nice, 1997, pp. 94-103; Discrete Comput. Geom. 20 (1998) 375-388.; Gy. Károlyi, J. Pach, G. Tóth, P. Valtr, Ramsey-type results for geometric graphs. II, Proc. 13th Annu. ACM Symp. on Computational Geometry, Nice, 1997, pp. 94-103; Discrete Comput. Geom. 20 (1998) 375-388. · Zbl 0912.05046 |
| [18] | Radziszowski, S. P., Small Ramsey numbers, Electron. J. Combin., 1, DS1, 27 (1994) · Zbl 0953.05048 |
| [19] | Ramsey, F. P., On a problem of formal logic, Proc. London Math. Soc., 30, 264-286 (1930) · JFM 55.0032.04 |
| [20] | Rosta, V., On a Ramsey type problem of J.A. Bondy and P. Erdős. I-II, J. Combin. Theory B, 15, 94-120 (1973) · Zbl 0261.05119 |
| [21] | Schur, I., Über die Kongruenz \(x^m+y^m\)≡ \(z^m\) ( modp)\), Jahresber. Deutschen Math.-Verein., 25, 114-116 (1916) · JFM 46.0193.02 |
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.
