A Note on Covering Edge Colored Hypergraphs by Monochromatic Components

Shinya Fujita, Michitaka Furuya, András Gyárfás, Ágnes Tóth

Abstract


For $r\geq 2$, $\alpha \geq r-1$ and $k\geq 1$, let $c(r,\alpha ,k)$ be the smallest integer $c$ such that the vertex set of any non-trivial $r$-uniform $k$-edge-colored hypergraph ${\cal H}$ with $\alpha ({\cal H})=\alpha$ can be covered by $c$ monochromatic connected components. Here $\alpha({\cal{H}})$ is the maximum cardinality of a subset $A$ of vertices in $\cal{H}$ such that $A$ does not contain any edges. An old conjecture of Ryser is equivalent to $c(2,\alpha,k)=\alpha (r-1)$ and a recent result of Z. Király states that $c(r,r-1,k)=\lceil \frac{k}{r}\rceil$ for any $r\ge 3$.

Here we make the first step to treat non-complete hypergraphs, showing that $c(r,r,r)=2$ for $r\ge 2$ and $c(r,r,r+1)=3$ for $r\ge 3$.


Keywords


Graph theory; edge-coloring; monochromatic component

Full Text: PDF