New upper bound for Gallai-Ramsey number of brooms - Pascoal, Matheus A. S. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.8080, 2025)
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 B l,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 GR k (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, GR k (B l,m ) ≤ (k − 2)(⌈l/2⌉ − 1)+3m−⌈3l/2⌉−2. We prove that if m ≥ 2 and l ≥ max{2m, 5} GR k (B l,m ) ≤ (k − 2)(⌈l/2⌉ − 1) + 3m + 3⌈l/2⌉ − 2.