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

Resumo

Dado grafos G e H, dizemos que G é H-good se o número de Ramsey R(G,H) for igual ao limitante inferior trivial (|G| − 1)(χ(H) − 1) + σ(H), onde χ(H) denota o número cromático usual de H, e σ(H) denota o tamanho mínimo de uma classe de cor em uma χ(H)-coloração de H. Em 2013, Allen et al. conjecturaram que P_n é H-good para todo n ≥ χ(H)|H|. Um resultado de Pokrovskiy e Sudakov (2017) implica que tal conjectura vale quando χ(H) ≥ 4. Nós estudamos o caso χ(H) = 2 e provamos que P_n é H-good para todo n ≥ 2 · |V(H)|, com H ⊆ K_3,t.

Referências

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.