2017/10/28 by Wu, Haibo, Magnant, Colton, Nowbandegani, Pouria Salehi +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.10455
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 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 all bipartite graphs with two vertices in one part and initiate the study of linear forests.