All partitions have small parts - Gallai-Ramsey numbers of bipartite graphs

摘要

Gallai-colorings are edge-colored complete graphs in which there are no rainbow triangles. Within such colored complete graphs, we consider Ramsey-type questions, looking for specified monochromatic graphs. In this work, we consider monochromatic bipartite graphs since the numbers are known to grow more slowly than for non-bipartite graphs. The main result shows that it often suffices to consider only 3-colorings which have a special partition of the vertices. Using this tool, we find several sharp numbers and conjecture the sharp value for all bipartite graphs. In particular, we determine the Gallai-Ramsey numbers for many bipartite graphs with two vertices in one part and initiate the study of linear forests. (C) 2018 Elsevier B.V. All rights reserved.