Edge coloring complete uniform hypergraphs with many components

2002/02/22 by Yair Caro, Caro, Yair, Raphael Yuster +1
Mathematics · #05c15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05c15

paper · pdf · doi:10.48550/arxiv.math/0202231

14 pages

arxiv created 2002/02/22 · arxiv updated 2009/11/30

Abstract

Let H be a hypergraph. For a k-edge coloring c : E(H) → \1,...,k\ let f(H,c) be the number of components in the subhypergraph induced by the color class with the least number of components. Let f_k(H) be the maximum possible value of f(H,c) ranging over all k-edge colorings of H. If H is the complete graph K_n then, trivially, f₁(K_n)=f₂(K_n)=1. In this paper we prove that for n ≥ 6, f₃(K_n)=\lfloor n/6 \rfloor+1 and supply close upper and lower bounds for f_k(K_n) in case k ≥ 4. Several results concerning the value of f_k(K_n^r), where K_n^r is the complete r-uniform hypergraph on n vertices, are also established.

Related

• Coloring H-free Hypergraphs
• On some generalizations of the property B-problem of an n-uniform hypergraph
• Large monochromatic components in colorings of complete hypergraphs
• The Maximum Number of Cliques in Hypergraphs without Large Matchings
• On a problem of Brown, Erdős and Sós