Gallai-Ramsey numbers for rainbow \(S_3^+\) and monochromatic paths
For two finite simple graphs \(G\) and \(H\), the \(k\)-colored Gallai-Ramsey number for edge-colorings, denoted \(\operatorname{gr}_k(G : H)\), is defined to be the minimum positive integer \(n\) such that every \(k\)-coloring of the complete graph on \(n\) vertices contains either a rainbow copy of \(G\) (i.e., no two edges have the same color) or a monochromatic copy of \(H\) (i.e., all the edges have the same color). Let \(S_3^+\) be the graph on four vertices consisting of a triangle with a pendant edge. In the paper under review, it is shown that \(\operatorname{gr}_k(S_3^+ : P_5) = k +4\) for \(k \geq 5\), where \(P_n\) is a path of length \(n\), \(\operatorname{gr}_k(S_3^+ : mP_2) = (m-1)k +m+1\) for \(k \geq 1\), where \(mP_n\) denotes the union of \(n\) disjoint copies of \(P_n\), \(\operatorname{gr}_k(S_3^+ : P_3 \cup P_2) = k + 4\) for \(k \geq 5\), and \(\operatorname{gr}_k(S_3^+ : 2P_3) = k + 5\) for \(k \geq 1\).
scientific article; zbMATH DE number 7495512