%0 Journal Article
%T Gallai-Colorings of Triples and 2-Factors of
%A Lynn Chua
%A Andr¨¢s Gy¨¢rf¨¢s
%A Chetak Hossain
%J International Journal of Combinatorics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/929565
%X A coloring of the edges of the -uniform complete hypergraph is a -coloring if there is no rainbow simplex; that is, every set of vertices contains two edges of the same color. The notion extends -colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of -colorings is that at least one color class has a spanning tree. J. Lehel and the senior author observed that this property does not hold for -colorings and proposed to study , the size of the largest monochromatic component which can be found in every -coloring of , the complete -uniform hypergraph. The previous remark says that and in this note, we address the case . We prove that and this determines for . We also prove that by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements. 1. Introduction Studying edge colorings of complete graphs without rainbow triangles (no triangles colored with distinct colors) originates from a famous paper of Gallai [1]; we will refer to such colorings as Gallai-colorings or -colorings. A well-known property of -colorings is that the edges of some color class span a connected subgraph containing all vertices. A natural extension of the concept is the -coloring, of , the complete -uniform hypergraph on vertices. In a -coloring the requirement is that no is colored with distinct colors; that is, there is no rainbow simplex. For , -colorings of do not necessarily contain spanning connected color classes, but they must contain large ones. To define how large, let be the size of the largest monochromatic component which can be found in every -coloring of . In terms of this function, , and in this note we address . Theorem 1. . Proof. The upper bound (an unpublished note of the senior author and J. Lehel) follows from taking first the -coloring of with five colors, where the vertex set is , and the edges , , and , , are colored with (using (mod 5) arithmetic). This coloring can be ¡°blown up¡± by replacing each vertex by a set so that the five sets have sizes that differ by at most one and defining the following straightforward extension of the original 5-coloring. Triples with vertices from three different are colored according to the color of the triple of their indices. Triples inside and triples in or in (with at least one vertex in each) are colored with color . The lower bound follows from the observation that every 4-set must contain two 3-sets of the same color. Thus the color of some 3-set is repeated on another triple inside at least 4-sets containing . This means
%U http://www.hindawi.com/journals/ijcom/2013/929565/