A note on covering edge colored hypergraphs by monochromatic components

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

¹Yokohama City University

The electronic journal of combinatorics, Tome 21 (2014) no. 2

Résumé

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$.

Détail

DOI : 10.37236/4137

Classification : 05C15, 05C65, 05C70
Mots-clés : edge-coloring, monochromatic component