Covering complete $r$-partite hypergraphs with few monochromatic components

Abstract

An edge-coloring of a hypergraph is {\em spanning} if every vertex sees every color used in the coloring. In this paper, we prove that for $k\ge 2r\ge 6$, in any spanning $k$-coloring of the edges of a complete $r$-partite $r$-uniform hypergraph $H$, the vertices of $H$ can be covered by a set of at most $k-r+1$ monochromatic connected components. This proves a conjecture of Gyárfás and Király which is related to a special case of Ryser's conjecture. We also prove that for $k\in \{2,3\}$, every spanning $k$-edge-coloring of a complete bipartite graph admits a covering of its vertices using at most $k$ monochromatic components.

9 pages, 2 figures