Ramsey‐type results for Gallai colorings

A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2⩽ d , or complete bipartite graphs. It follows that every Gallai‐colored K n contains a monochromatic double star with at least 3 n + 1/4 vertices, a monochromatic complete bipartite graph on at least n /2 vertices, monochromatic subgraphs of diameter two with at least 3 n /4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n /2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization . We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG ( r, H ) be the minimum m such that in every Gallai‐coloring of K m with r colors, there is a monochromatic copy of H . We show that for fixed H , RG ( r, H ) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r ) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010