A variant of the Erdős–Rényi random graph process

We consider a natural variant of the Erdős–Rényi random graph process in whichk $k$ vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the multiway cut problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition for the appearance of the giant component occurs when the number of special vertices is roughlyn 1 ∕ 3${n}^{1\unicode{x02215}3}$ , wheren $n$ is the number of vertices.