Effective bounds for induced size-Ramsey numbers of cycles
EUROCOMB’23
193–200
Noga Alon. Explicit Ramsey graphs and orthonormal labelings. The Electronic Journal of Combinatorics, pages R12-R12, 1994.
https://doi.org/10.37236/1192
József Beck. On size Ramsey number of paths, trees, and circuits. I. Journal of Graph Theory, 7(1):115-129, 1983.
https://doi.org/10.1002/jgt.3190070115
D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory. In: Surveys in Combinatorics 2015, Cambridge University Press, 2015, 49-118.
https://doi.org/10.1017/CBO9781316106853.003
W. Deuber, A generalization of Ramsey's theorem. In: Infinite and Finite Sets, Vol.1, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland, Amsterdam/London, 1975, 323-332.
Nemanja Draganić, Stefan Glock, and Michael Krivelevich. Short proofs for long induced paths. Combinatorics, Probability and Computing, 31(5):870-878, 2022.
https://doi.org/10.1017/S0963548322000013
Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov. Rolling backwards can move you forward: on embedding problems in sparse expanders. Transactions of the American Mathematical Society, 2022.
https://doi.org/10.1090/tran/8660
Nemanja Draganić and Kalina Petrova. Size-Ramsey numbers of graphs with maximum degree three. arXiv preprint arXiv:2207.05048, 2022.
Andrzej Dudek and Paweł Prałat. An alternative proof of the linearity of the size-Ramsey number of paths. Combinatorics, Probability and Computing, 24(3):551-555, 2015.
https://doi.org/10.1017/S096354831400056X
Andrzej Dudek and Paweł Prałat. On some multicolor Ramsey properties of random graphs. SIAM Journal on Discrete Mathematics, 31(3):2079-2092, 2017.
https://doi.org/10.1137/16M1069717
Paul Erdős. Problems and results on finite and infinite graphs. In Recent Advances in Graph Theory. Proceedings of the Second Czechoslovak Symposium, pages 183-192. Academia, Prague, 1975.
Paul Erdős, Ralph J. Faudree, Cecil C. Rousseau, and Richard H. Schelp. The size Ramsey number. Periodica Mathematica Hungarica, 9(1-2):145-161, 1978.
https://doi.org/10.1007/BF02018930
P. Erdős, A. Hajnal, and L. Pósa. Strong embeddings of graphs into colored graphs. In: Infinite and Finite Sets, Vol. 1, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland, Amsterdam/London, 1975, 585-595.
Jacob Fox and Benny Sudakov. Induced Ramsey-type theorems. Advances in Mathematics, 219(6):1771-1800, 2008.
https://doi.org/10.1016/j.aim.2008.07.009
Joel Friedman and Nicholas Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71-76, 1987.
https://doi.org/10.1007/BF02579202
Penny E. Haxell, Yoshiharu Kohayakawa, and Tomasz Łuczak. The induced size-Ramsey number of cycles. Combinatorics, Probability and Computing, 4(3):217-239, 1995.
https://doi.org/10.1017/S0963548300001619
Ramin Javadi, Farideh Khoeini, Gholam Reza Omidi, and Alexey Pokrovskiy. On the size-Ramsey number of cycles. Combinatorics, Probability and Computing, 28(6):871-880, 2019.
https://doi.org/10.1017/S0963548319000221
Ramin Javadi and Meysam Miralaei. The multicolor size-Ramsey numbers of cycles. Journal of Combinatorial Theory, Series B, 158:264-285, 2023.
https://doi.org/10.1016/j.jctb.2022.10.003
Nina Kamčev, Anita Liebenau, David R. Wood, and Liana Yepremyan. The size Ramsey number of graphs with bounded treewidth. SIAM Journal on Discrete Mathematics, 35(1):281-293, 2021.
https://doi.org/10.1137/20M1335790
Yoshiharu Kohayakawa, Hans Jürgen Promel, and Vojtěch Rödl. Induced Ramsey numbers. Combinatorica, 18(3):373-404, 1998.
https://doi.org/10.1007/PL00009828
Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Endre Szemerédi. Sparse partition universal graphs for graphs of bounded degree. Advances in Mathematics, 226(6):5041-5065, 2011.
https://doi.org/10.1016/j.aim.2011.01.004
Michael Krivelevich. Expanders-how to find them, and what to find in them. In: Surveys in combinatorics 2019, volume 456 of London Mathematical Society Lecture Note Series, pages 115-142. Cambridge University Press, Cambridge, 2019.
https://doi.org/10.1017/9781108649094.005
Michael Krivelevich. Long cycles in locally expanding graphs, with applications. Combinatorica, 39(1):135-151, 2019.
https://doi.org/10.1007/s00493-017-3701-1
Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30(4):264-286, 1929.
https://doi.org/10.1112/plms/s2-30.1.264
Vojtěch Rödl. The dimension of a graph and generalized Ramsey theorems, Master's thesis, Charles University, 1973.
Vojtěch Rödl and Endre Szemerédi. On size Ramsey numbers of graphs with bounded degree. Combinatorica, 20(2):257-262, 2000.
https://doi.org/10.1007/s004930070024
Konstantin Tikhomirov. On bounded degree graphs with large size-Ramsey numbers. arXiv preprint arXiv:2210.05818, 2022.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Domagoj Bradac, Nemanja Draganic, Benny Sudakov