Coloring the edges of a random graph without a monochromatic giant component (Q5917953)

Summary: We study the following two problems: {\parindent=6mm \begin{itemize}\item[i)]Given a random graph \(G_{n,m}\) (a graph drawn uniformly at random from all graphs on \(n\) vertices with exactly \(m\) edges), can we color its edges with \(r\) colors such that no color class contains a component of size \(\Theta(n)\)? \item[ii)]Given a random graph \(G_{n,m}\) with a random partition of its edge set into sets of size \(r\), can we color its edges with \(r\) colors subject to the restriction that every color is used for exactly one edge in every set of the partition such that no color class contains a component of size \(\Theta(n)\)? \end{itemize}} We prove that for any fixed \(r\geq 2\), in both settings the (sharp) threshold for the existence of such a coloring coincides with the known threshold for \(r\)-orientability of \(G_{n,m}\), which is at \(m=rc_r^*n\) for some analytically computable constant \(c_r^*\). The fact that the two problems have the same threshold is in contrast with known results for the two corresponding Achlioptas-type problems.