Title of article :
Edge coloring complete uniform hypergraphs with many components
Author/Authors :
Caro، نويسنده , , Yair and Yuster، نويسنده , , Raphael، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
13
From page :
215
To page :
227
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 fk(H) be the maximum possible value of f(H,c) ranging over all k-edge colorings of H. If H is the complete graph Kn then, trivially, f1(Kn)=f2(Kn)=1. In this paper we prove that for n⩾6,f3(Kn)=⌊n/6⌋+1 and supply close upper and lower bounds for fk(Kn) in case k⩾4. Several results concerning the value of fk(Knr), where Knr is the complete r-uniform hypergraph on n vertices, are also established.
Keywords :
Hypergraph , Coloring , components
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2004
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527444
Link To Document :
بازگشت