Ramsey Goodness of paths versus K3,t

• Fábio Botler USP
• Luiz Paulo Freire Moreira UFPE
• João Pedro de Souza Colégio Pedro II / UFRJ

DOI: https://doi.org/10.5753/etc.2025.8433

Abstract

Given graphs G and H, we say that G is H-good if the Ramsey number R(G,H) equals the trivial lower bound (|G|−1)(χ(H)−1)+σ(H), where χ(H) denotes the usual chromatic number of H, and σ(H) denotes the minimum size of a color class in a χ(H)-coloring of H. In 2013, Allen, Brightwell, and Skokan conjectured that P_n is H-good for every n ≥ χ(H)|H|. A result of Pokrovskiy and Sudakov (2017) implies that this conjecture holds when χ(H) ≥ 4. We study the case χ(H) = 2 and show that P_n is H-good for n ≥ 2 · |V(H)|, with H ⊆ K_3,t.

References

Allen, P., Brightwell, G., and Skokan, J. (2013). Ramsey-goodness—and otherwise. Combinatorica, 33:125–160.

Balla, I., Pokrovskiy, A., and Sudakov, B. (2018). Ramsey goodness of bounded degree trees. Combinatorics, Probability and Computing, 27(3):289–309.

Botler, F., Moreira, L., and de Souza, J. P. (2024). Ramsey goodness of paths and unbalanced graphs. arXiv preprint arXiv:2410.19942.

Botler, F. H., Collares, M., Martins, T., Mendonça, W., Morris, R., and Mota, G. O. (2022). Combinatória. IMPA.

Brandt, S., Broersma, H., Diestel, R., and Kriesell, M. (2006). Global connectivity and expansion: long cycles and factors in F-connected graphs. Combinatorica, 26:17–36.

Burr, S. A. (1981). Ramsey numbers involving graphs with long suspended paths. Journal of the London Mathematical Society, 2(3):405–413.

Burr, S. A. and Erdős, P. (1983). Generalizations of a Ramsey-theoretic result of Chvátal. Journal of Graph Theory, 7(1):39–51.

Chvátal, V. (1977). Tree-complete graph Ramsey numbers. Journal of Graph Theory, 1(1):93–93.

Conlon, D., Fox, J., and Sudakov, B. (2015). Recent developments in graph Ramsey theory. Surveys in combinatorics, 424(2015):49–118.

Erdős, P., Faudree, R. J., Rousseau, C. C., and Schelp, R. H. (1985). Multipartite graph—sparse graph Ramsey numbers. Combinatorica, 5:311–318.

Moreira, L. (2021). Ramsey goodness of clique versus paths in random graphs. SIAM Journal on Discrete Mathematics, 35(3):2210–2222.

Nikiforov, V. and Rousseau, C. C. (2009). Ramsey goodness and beyond. Combinatorica, 29:227–262.

Pokrovskiy, A. and Sudakov, B. (2017). Ramsey goodness of paths. Journal of Combinatorial Theory, Series B, 122:384–390.

Pokrovskiy, A. and Sudakov, B. (2020). Ramsey goodness of cycles. SIAM Journal on Discrete Mathematics, 34(3):1884–1908.