Rainbow monochromatic $k$-edge-connection colorings of graphs

Abstract

A path in an edge-colored graph is called a monochromatic path if all edges of the path have a same color. We call $k$ paths $P_1,\cdots ,P_k$ rainbow monochromatic paths if every $P_i$ is monochromatic and for any two $i\ne j$, $P_i$ and $P_j$ have different colors. An edge-coloring of a graph $G$ is said to be a rainbow monochromatic $k$-edge-connection coloring (or $RM{C}_k$-coloring for short) if every two distinct vertices of $G$ are connected by at least $k$ rainbow monochromatic paths. We use $rm{c}_k(G)$ to denote the maximum number of colors that ensures $G$ has an $RM{C}_k$-coloring, and this number is called the rainbow monochromatic $k$-edge-connection number. We prove the existence of $RM{C}_k$-colorings of graphs, and then give some bounds of $rm{c}_k(G)$ and present some graphs whose $rm{c}_k(G)$ reaches the lower bound. We also obtain the threshold function for $rm{c}_k(G(n,p))\ge f(n)$, where $\lfloor \frac{n}{2}\rfloor >k\ge 1$.

22 pages