New upper bound for Gallai-Ramsey number of brooms
Resumo
Let m, l, and k be integers greater than 1. The broom graph with a handle of length l and m bristles is denoted by Bl,m. A Gallai coloring of a graph G is an edge coloring of G that does not have a triangle with edges of 3 distinct colors. The k-colored Gallai-Ramsey number of the graph H denoted by GRk(H) is the smallest natural number n such that every Gallai k-coloring of the complete graph with n vertices contains a monochromatic copy of H . Hamlin proved in 2019 that, for m ≥ 7l/2 + 3, GRk(Bl,m) ≤ (k − 2)(⌈l/2⌉ − 1)+3m−⌈3l/2⌉−2. We prove that if m ≥ 2 and l ≥ max{2m, 5} GRk(Bl,m) ≤ (k − 2)(⌈l/2⌉ − 1) + 3m + 3⌈l/2⌉ − 2.
Referências
Campos, M., Griffiths, S., Morris, R., and Sahasrabudhe, J. (2023). An exponential improvement for diagonal Ramsey.
Erdős, P., Faudree, R., Schelp, R., and Rousseau, C. (1982). Ramsey numbers of brooms. Proceedings of the Thirteenth Southeastern Conference on Combinatorics, Graph Theory and Computing.
Gyárfás, A. and Simony, G. (2004). Edge colorings of complete graphs without tricolored triangles. Journal of Graph Theory, 46:211–216.
Hall, M., Magnant, C., Ozeki, K., and Tsugaki, M. (2014). Improved upper bounds for Gallai–Ramsey numbers of paths and cycles. Journal of Graph Theory, 75(1):59–74.
Hamlin, B. J. (2019). Gallai-Ramsey number for classes of brooms. Master’s thesis, Georgia Southern University.
Jackson, B. (1981). Cycles in bipartite graphs. Journal of Combinatorial Theory, 30:332–342.
Radziszowski, S. (2012). Small Ramsey numbers. The Electronic Journal of Combinatorics, pages DS1–Jan.
Ramsey, F. P. (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286.
Rosta, V. (2004). Ramsey Theory applications. The Electronic Journal of Combinatorics, 1000:DS13–Dec.
Wu, H., Magnant, C., Salehi Nowbandegani, P., and Xia, S. (2019). All partitions have small parts Gallai-Ramsey numbers of bipartite graphs. Discrete Applied Mathematics, 254:196–203.
Yu, P. and Li, Y. (2016). All Ramsey numbers for brooms in graphs. The Electronic Journal of Combinatorics, 23:P3–29.
Zhang, F., Song, Z.-X., and Chen, Y. (2022). Gallai-ramsey number of even cycles with chords. Discrete Mathematics, 345(3):112738.
Erdős, P., Faudree, R., Schelp, R., and Rousseau, C. (1982). Ramsey numbers of brooms. Proceedings of the Thirteenth Southeastern Conference on Combinatorics, Graph Theory and Computing.
Gyárfás, A. and Simony, G. (2004). Edge colorings of complete graphs without tricolored triangles. Journal of Graph Theory, 46:211–216.
Hall, M., Magnant, C., Ozeki, K., and Tsugaki, M. (2014). Improved upper bounds for Gallai–Ramsey numbers of paths and cycles. Journal of Graph Theory, 75(1):59–74.
Hamlin, B. J. (2019). Gallai-Ramsey number for classes of brooms. Master’s thesis, Georgia Southern University.
Jackson, B. (1981). Cycles in bipartite graphs. Journal of Combinatorial Theory, 30:332–342.
Radziszowski, S. (2012). Small Ramsey numbers. The Electronic Journal of Combinatorics, pages DS1–Jan.
Ramsey, F. P. (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286.
Rosta, V. (2004). Ramsey Theory applications. The Electronic Journal of Combinatorics, 1000:DS13–Dec.
Wu, H., Magnant, C., Salehi Nowbandegani, P., and Xia, S. (2019). All partitions have small parts Gallai-Ramsey numbers of bipartite graphs. Discrete Applied Mathematics, 254:196–203.
Yu, P. and Li, Y. (2016). All Ramsey numbers for brooms in graphs. The Electronic Journal of Combinatorics, 23:P3–29.
Zhang, F., Song, Z.-X., and Chen, Y. (2022). Gallai-ramsey number of even cycles with chords. Discrete Mathematics, 345(3):112738.
Publicado
20/07/2025
Como Citar
PASCOAL, Matheus A. S..
New upper bound for Gallai-Ramsey number of brooms. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 31-35.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.8080.
