A Note on Covering Edge Colored Hypergraphs by Monochromatic Components

  • Shinya Fujita
  • Michitaka Furuya
  • András Gyárfás
  • Ágnes Tóth
Keywords: Graph theory, edge-coloring, monochromatic component

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

Published
2014-05-13
Article Number
P2.33