Gallai and [formula omitted]-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 G R 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 ℓ , the ℓ -uniform Ramsey number R k ℓ (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 ℓ , contains a monochromatic copy of H. Let K m , n denote a complete bipartite graph. Wu et al. conjectured that G R k (K m , n) = (n − 1) (k − 2) + R 2 1 (K m , n) if R 2 1 (K m , n) ≥ 3 m − 2 , where k ≥ 3 and m ≥ n ≥ 2. In this paper, we show that G R k (K m , n) = (n − 1) (k − 2) + R 2 m − 1 (K m , n) for all integers k ≥ 3 and m ≥ n ≥ 2. Based on this result, we improve the known general bounds for G R k (K m , n) , and confirm the conjecture for some complete bipartite graphs. [ABSTRACT FROM AUTHOR]