Angle-resolved photoemission spectroscopy reveals pronounced kinks in the dispersion of the band of graphene. Such kinks are usually caused by the combination of a strong electron-boson interaction and the cutoff in the Fermi-Dirac distribution. They are therefore not expected for the band of graphene that has a binding energy of more than 3:5 eV. We argue that the observed kinks are indeed caused by the electron-phonon interaction, but the role of the Fermi-Dirac distribution cutoff is assumed by a cutoff in the density of states. The existence of the effect suggests a very weak coupling of holes in the band not only to the electrons of graphene but also to the substrate electronic states. This is confirmed by the presence of such kinks for graphene on several different substrates that all show a strong coupling constant of 1.