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 H without multicolored triangles contain monochromatic connected subgraphs with at least (α(H)²+α(H)−1)⁻¹|V(H)| vertices, where α(H) is the independence number of H. In general, we show that if the edges of an r-uniform hypergraph H are colored so that there is no multicolored copy of a fixed F then there is a monochromatic connected subhypergraph H₁⊆H such that |V(H₁)|≥c|V(H)| where c depends only on F, r, and α(H).