The dynamics of the graphene-catalyst interaction during chemical vapor deposition are investigated using in situ, time- and depth-resolved X-ray photoelectron spectroscopy, and complementary grand canonical Monte Carlo simulations coupled to a tight-binding model. We thereby reveal the interdependency of the distribution of carbon close to the catalyst surface and the strength of the graphene-catalyst interaction. The strong interaction of epitaxial graphene with Ni(111) causes a depletion of dissolved carbon close to the catalyst surface, which prevents additional layer formation leading to a self-limiting graphene growth behavior for low exposure pressures (10(-6)-10(-3) mbar). A further hydrocarbon pressure increase (to similar to 10(-1) mbar) leads to weakening of the graphene-Ni(111) interaction accompanied by additional graphene layer formation, mediated by an increased concentration of near-surface dissolved carbon. We show that growth of more weakly adhered, rotated graphene on Ni(111) is linked to an initially higher level of near-surface carbon compared to the case of epitaxial graphene growth. The key implications of these results for graphene growth control and their relevance to carbon nanotube growth are highlighted in the context of existing literature.