2019/02/14 by Cao, Shujuan, Ma, Yuede, Taoqiu, Zhenyu
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1902.05222
For a fixed graph F and an integer t, the \dfnrainbow saturation number of F, denoted by satt(n,\mathfrakR(F)), is defined as the minimum number of edges in a t-edge-colored graph on n vertices which does not contain a \dfnrainbow copy of F, i.e., a copy of F all of whose edges receive a different color, but the addition of any missing edge in any color from [t] creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that satt(n,\mathfrakR(P_ℓ))≥ n-1 for ℓ≥ 4 and satt(n,\mathfrakR(P_ℓ))≤ \lceil (n)/(ℓ-1) \rceil ⋅ \binomℓ-12 for t≥ \binomℓ-12, where P_ℓ is a path with ℓ edges. In this short note, we improve the upper bounds and show that satt(n,\mathfrakR(P_ℓ))≤ \lceil (n)/(ℓ) \rceil ⋅ (ℓ-2\choose 2+4) for ℓ≥ 5 and t≥ 2ℓ-5.