## Covering complete partite hypergraphs by monochromatic components

#### András Gyárfás, Zoltán Király

Published in:
Discrete Mathematics, Volume 340, Issue 12, 2017, Pages 2753-2761. DOI link

### Abstract

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson \cite{HE}) states that $k$-partite intersecting hypergraphs have transversals of at most $k-1$ vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in \cite{GY1}: if the edges of a complete graph $K$ are colored with $k$ colors then the vertex set of $K$ can be covered by at most $k-1$ sets, each connected in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: Z. Király proved \cite{KI} that in every $k$-coloring of the edges of the $r$-uniform complete hypergraph $K^r$ ($r\ge 3$), the vertex set of $K^r$ can be covered by at most $\lceil k/r \rceil$ sets, each connected in some color.

Here we investigate the analogue problem for complete $r$-uniform $r$-partite hypergraphs. An edge coloring of a hypergraph is called {\bf spanning} if every vertex is incident to edges of any color used in the coloring. We propose the following analogue of Ryser conjecture.

\noindent {\em In every spanning $(r+t)$-coloring of the edges of a complete $r$-uniform $r$-partite hypergraph, the vertex set can be covered by at most $t+1$ sets, each connected in some color.}

We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for $1\le t\le r-1$. We also prove a slightly weaker result for $t\ge r$, namely that $t+2$ sets, each connected in some color, are enough to cover the vertex set.

To build a bridge between complete $r$-uniform and complete $r$-uniform $r$-partite hypergraphs, we introduce a new notion. A hypergraph is complete $r$-uniform $(r,\ell)$-partite if it has all $r$-sets that intersect each partite class in at most $\ell$ vertices (where $1\le\ell\le r$).

Extending our results achieved for $\ell=1$, we prove that for any $r\ge 3,\; 2\le\ell\le r,\; k\ge 1+r-\ell$, in every spanning $k$-coloring of the edges of a complete $r$-uniform $(r,\ell)$-partite hypergraph, the vertex set can be covered by at most $1+\lfloor \frac{k-r+\ell-1}{\ell}\rfloor$ sets, each connected in some color.

Bibtex entry:

@techreport{egres-16-03,
AUTHOR = {Gy{\'a}rf{\'a}s, Andr{\'a}s and Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Covering complete partite hypergraphs by monochromatic components},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-03}
}