FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
No date set
Covering edge multicolorings of complete graphs with monochromatic connected components
Sebastián Bustamante
Universidad de Chile, Chile - sbustamante@dim.uchile.cl
Let $K_n$ denote the complete graph on vertex set $V = [n].$ An $r$-edge multicoloring is a coloring of the edges with any number of colors in $[r].$ If every edge is colored by a constant number $k$ of colors, we say that the $r$-edge multicoloring is $k$-regular. The connected components of the monochromatic graphs given by $G_i = (V_i,E_i),$ with $e \in E_i$ if the edge $e$ has the color $i,$ for $i \in [r],$ are called monochromatic connected components. For $r > k,$ let $f(r,k)$ the smallest number such that, for any $k$-regular $r$-edge multicoloring of a complete graph, it is possible to cover the complete graph by $f(r,k)$ monochromatic connected components. A reformulation of an important special case of Ryser's conjecture states that $f(r,1) = r-1$ for all $r.$ This conjecture is known to be true for $r \leq 5.$ We prove, for $k \geq 2,$ several exact values and bounds for $f(r,k),$ and a related result of independent interest, as the maximum number of vertices for a vertex minimal $r$-edge multicoloring of a complete graph coverable by three, but no by two, monochromatic connected components.
Joint work with Maya Stein (Universidad de Chile, Chile).