2024/10/02 by Zhang, Yanbo, Chen, Yaojun
#05C55 #05D10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.01549
As a significant variation of Ramsey numbers, the Gallai-Ramsey number GRk(H) refers to the smallest positive integer r such that, by coloring the edges of Kr with at most k colors, there exists either a monochromatic subgraph isomorphic to H or a rainbow triangle. Mao, Wang, Magnant, and Schiermeyer [Discrete Math., 2023], Song, Wei, Zhang, and Zhao [Discrete Math., 2020], and Zhao and Wei [Discrete Appl. Math., 2021] each proposed one conjecture on the Gallai-Ramsey numbers for fans, wheels, and kipases, respectively. We establish new lower bounds that disprove all three conjectures. Su and Liu [Graphs Combin., 2022] studied the Gallai-Ramsey-full property of graphs and conjectured that a graph is Ramsey-full if and only if it is Gallai-Ramsey-full. We present two classes of graphs that are Ramsey-full, but neither is Gallai-Ramsey-full.