کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423985 | 1632593 | 2011 | 5 صفحه PDF | دانلود رایگان |
Let Knr denote the complete r-uniform hypergraph on vertex set V=[n]. An f-coloring is a coloring of the edges with colors {1,2,â¦,f}, it defines monochromatic r-uniform hypergraphs Hi=(V,Ei) for i=1,â¦,f, where Ei contains the r-tuples colored by i. The connected components of hypergraphs Hi are called monochromatic components. For n>rk let f(n,r,k) denote the maximum number of colors, such that in any f-coloring of Knr, there exist k monochromatic components covering V. Moreover let f(r,k)=minn>rkf(n,r,k). A reformulation (see [A. Gyárfás Partition coverings and blocking sets in hypergraphs, Commun. Comput. Autom. Inst. Hungar. Acad. Sci. 71 (1977)]) of an important special case of Ryserʼs conjecture states that f(2,k)=k+1 for all k. This conjecture is proved to be true only for k⩽4, so the value of f(2,5) is not known. On the contrary, in this paper we show that for r>2 we can determine f(r,k) exactly, and its value is rk.
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 517-521