Gallai and l-uniform Ramsey numbers of complete bipartite graphs

A Gallai coloring of a complete graph is a coloring of the edges without rainbow triangles (all edges colored differently). Given a graph H and a positive integer k, the Gallai Ramsey number GR(k)(H) is the minimum integer N such that every Gallai k-coloring of K-N contains a monochromatic copy of H. A uniform coloring of a complete multipartite graph is a coloring of the edges such that the edges between any two parts receive the same color. Given a graph H and positive integers k and l, the l-uniform Ramsey number R-k(l) (H) is the minimum integer N such that any uniform k-coloring of any complete multipartite graph on N vertices with each part of cardinality no more than l, contains a monochromatic copy of H. Let K-m,K- n denote a complete bipartite graph. Wu et al. conjectured that GR(k)(K-m,K-n) = (n - 1)(k - 2)+ R-2(1)(K-m,K-n) if R-2(1) (K-m,K-n) >= 3m - 2, where k >= 3 and m >= n >= 2. In this paper, we show that GR(k)(K-m,K-n) = (n - 1)(k - 2) + R-2(m-1) (K-m,K-n) for all integers k >= 3 and m >= n >= 2. Based on this result, we improve the known general bounds for GR(k)(K-m,K-n), and confirm the conjecture for some complete bipartite graphs. (C) 2021 Elsevier B.V. All rights reserved.