|
Published in:
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:
| 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} |