The growth of high-density arrays of vertically oriented, single crystalline InAs NWs on graphene surfaces are realized through the van der Waals (vdW) epitaxy mechanism by metalorganic chemical vapor deposition (MOCVD). However, the growth of InGaAs NWs on graphene results in spontaneous phase separation starting from the beginning of growth, yielding a well-defined InAs-In(x)Ga(1-x)As (0.2 < x < 1) core-shell structure. The core-shell structure then terminates abruptly after about 2 μm in height, and axial growth of uniform composition In(x)Ga(1-x)As takes place without a change in the NW diameter. The In(x)Ga(1-x)As shell composition changes as a function of indium flow, but the core and shell thicknesses and the onset of nonsegregated In(x)Ga(1-x)As axial segment are independent of indium composition. In contrast, no InGaAs phase segregation has been observed when growing on MoS2, another two-dimensional (2D) layered material, or via the Au-assisted vapor-liquid-solid (VLS) mechanism on graphene. This spontaneous phase segregation phenomenon is elucidated as a special case of van der Waals epitaxy on 2D sheets. Considering the near lattice matched registry between InAs and graphene, InGaAs is forced to self-organize into InAs core and InGaAs shell segments since the lack of dangling bonds on graphene does not allow strain sharing through elastic deformation between InGaAs and graphene.