2019/02/02 by Li, Xihe, Besse, Pierre, Magnant, Colton +2 · 2 citations
#05C55 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1902.00612
Given graphs G and H and a positive integer k, the Gallai-Ramsey number, denoted by grk(G : H) is defined to be the minimum integer n such that every coloring of Kn using at most k colors will contain either a rainbow copy of G or a monochromatic copy of H. We consider this question in the cases where G ∈ \P4, P5\. In the case where G = P4, we completely solve the Gallai-Ramsey question by reducing to the 2-color Ramsey numbers. In the case where G = P5, we conjecture that the problem reduces to the 3-color Ramsey numbers and provide several results in support of this conjecture.