We calculate the potential energy surfaces for graphene adsorbed on Cu(111), Ni(111), and Co(0001) using density functional theory and the Random Phase Approximation (RPA). For these adsorption systems covalent and dispersive interactions are equally important and while commonly used approximations for exchange-correlation functionals give inadequate descriptions of either van der Waals or chemical bonds, RPA accounts accurately for both. It is found that the adsorption is a delicate competition between a weak chemisorption minimum close to the surface and a physisorption minimum further from the surface.