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 (alpha(H)(2) + alpha(H) - 1)(-1)vertical bar V(H)vertical bar vertices, where alpha(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-1 subset of H such that vertical bar V(H-1)vertical bar >= c vertical bar V(H)vertical bar where c depends only on F, r, and alpha(H). (C) 2009 Elsevier B.V. All rights reserved.