Coloring the edges of a random graph without a monochromatic giant component

Reto Spöhel ; Angelika Steger ; Henning Thomas

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We study the following two problems: 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)$? 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)$? 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.

Détail

DOI : 10.37236/405

Classification : 05C80, 05C15