Gallai colorings of non-complete graphs

Gallai-colorings of complete graphs–edge colorings such that no triangle is colored with three distinct colors–occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper), information theory and the theory of perfect graphs. We extend here Gallai-colorings to non-complete graphs and study the analogue of a basic result–any Gallai-colored complete graph has a monochromatic spanning tree–in this more general setting. We show that edge colorings of a graph HH without multicolored triangles contain monochromatic connected subgraphs with at least (α(H)2+α(H)−1)−1|V(H)|(α(H)2+α(H)−1)−1|V(H)| vertices, where α(H)α(H) is the independence number of HH. In general, we show that if the edges of an rr-uniform hypergraph HH are colored so that there is no multicolored copy of a fixed FF then there is a monochromatic connected subhypergraph H1⊆HH1⊆H such that |V(H1)|≥c|V(H)||V(H1)|≥c|V(H)| where cc depends only on FF, rr, and α(H)α(H).