New lower bounds on the size-Ramsey number of a path. (English) Zbl 1481.05106
Summary: We prove that for all graphs with at most \((3.75-o(1))n\) edges there exists a 2-coloring of the edges such that every monochromatic path has order less than \(n\). This was previously known to be true for graphs with at most \(2.5n-7.5\) edges. We also improve on the best-known lower bounds in the \(r\)-color case.
References:
| [1] | N. Alon. On the edge-expansion of graphs.Combinatorics, Probability and Computing 6, no. 2 (1997): 145-152. · Zbl 0881.05077 |
| [2] | N. Alon, P. Hamburger, and A. V. Kostochka. Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs.European Journal of Combinatorics20, no. 6 (1999): 469-481. · Zbl 0935.05053 |
| [3] | J. Balogh, A. Dudek, L. Li. An analogue of the Erd��os-Gallai theorem for random graphs.European Journal of Combinatorics91(2021), Paper No. 103200, 11 pp. · Zbl 1458.05236 |
| [4] | J. Balogh, A. Kostochka, M. Lavrov, and X. Liu. Monochromatic connected matchings in 2-edge-colored multipartite graphs.arXiv:1905.04653(2019). · Zbl 1433.05216 |
| [5] | J. Balogh, A. Kostochka, M. Lavrov, and X. Liu. Long monochromatic paths and cycles in 2-edge-colored multipartite graphs. Moscow Journal of Combinatorics and Number Theory9, no. 1 (2020): 55-100. · Zbl 1433.05216 |
| [6] | J. Beck. On size Ramsey number of paths, trees, and circuits. I.Journal of Graph Theory7, no. 1 (1983): 115-129. · Zbl 0508.05047 |
| [7] | J. Beck. On size Ramsey number of paths, trees and circuits. II.In Mathematics of Ramsey theory, pp. 34-45. Springer, Berlin, Heidelberg, 1990. · Zbl 0735.05056 |
| [8] | J. Bermond, J. Fouquet, M. Habib, and B. Peroche. On lineark-arboricity.Discrete Mathematics52, no. 2-3 (1984): 123-132. · Zbl 0556.05054 |
| [9] | H. Bielak. Remarks on the size Ramsey number of graphs.Periodica Mathematica Hungarica18, no. 1 (1987): 27-38. · Zbl 0617.05049 |
| [10] | B. Bollob´as. Extremal graph theory with emphasis on probabilistic methods. No. 62. American Mathematical Soc., 1986. · Zbl 0597.05038 |
| [11] | B. Bollob´as. Random graphs. No. 73. Cambridge University Press, 2001. · Zbl 0979.05003 |
| [12] | R. Diestel. Graph theory. Fifth edition. Graduate Texts in Mathematics, 173. Springer, Berlin, 2018. xviii+428 pp. |
| [13] | A. Dudek, F. Khoeini, P. Pra lat. Size-Ramsey numbers of cycles versus a path. Discrete Mathematics341, no. 7 (2018): 2095-2103. · Zbl 1387.05163 |
| [14] | A. Dudek, P. Pra lat. An alternative proof of the linearity of the size-Ramsey number of paths.Combinatorics, Probability and Computing24, no. 3 (2015): 551-555. · Zbl 1371.05172 |
| [15] | A. Dudek, P. Pra lat. On some multicolor Ramsey properties of random graphs.SIAM Journal on Discrete Mathematics31, no. 3 (2017): 2079-2092. · Zbl 1370.05211 |
| [16] | A. Dudek, P. Pra lat. Note on the Multicolour Size-Ramsey Number for Paths.Electronic Journal of Combinatorics25, no. 3, (2018): P3.35. · Zbl 1395.05179 |
| [17] | P. Erd˝os. On the combinatorial problems which I would most like to see solved. Combinatorica1, no. 1 (1981): 25-42. · Zbl 0486.05001 |
| [18] | A.M. Frieze, M. Karo´nski. Introduction to random graphs. Cambridge University Press, Cambridge, 2016. xvii+464 pp. · Zbl 1328.05002 |
| [19] | L. Gerencs´er and A. Gy´arf´as. On Ramsey-type problems.Ann. Univ. Sci. Budapest. E¨otv¨os Sect. Math10(1967): 167-170. · Zbl 0163.45502 |
| [20] | A. Gy´arf´as. Large monochromatic components in edge colorings of graphs: a survey. In Ramsey Theory, pp. 77-96. Birkh¨auser, Boston, MA, 2011. · Zbl 1221.05140 |
| [21] | R.Javadi,M.Miralaei.MulticolorSize-RamseyNumberofCycles. arXiv:2106.16023(2021). |
| [22] | M. Krivelevich. Long cycles in locally expanding graphs, with applications.Combinatorica39, no. 1 (2019): 135-151. · Zbl 1438.05142 |
| [23] | A. V. Kostochka, L. S. Melnikov. On bounds of the bisection width of cubic graphs. In Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, pp. 151-154. Elsevier, 1992. · Zbl 0773.05069 |
| [24] | S. Letzter. Path Ramsey number for random graphs.Combinatorics, Probability and Computing25, no. 4 (2016): 612-622. · Zbl 1372.05228 |
| [25] | C. McDiarmid. On the method of bounded differences.Surveys in combinatorics141, no. 1 (1989): 148-188. · Zbl 0712.05012 |
| [26] | A. Vince. The integrity of a cubic graph.Discrete Applied Mathematics140, no. 1-3 (2004): 223-239. · Zbl 1069.90018 |
| [27] | S. Yongqi, Y. Yuansheng, X. Feng, and L. Bingxi. New lower bounds on the multicolor Ramsey numbersRr(C2m).Graphs and Combinatorics22, no. 2 (2006): 283-288 · Zbl 1099.05062 |
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.
