Abstract: The spectrum of electron-phonon complexes in monolayer graphene is investigated in the presence of a perpendicular quantizing magnetic field. Despite the small electron-phonon coupling, usual perturbation theory is inapplicable for the calculation of the scattering amplitude near the threshold of optical phonon emission. Our findings, beyond perturbation theory, show that the true spectrum near the phonon-emission threshold is completely governed by new branches, corresponding to bound states of an electron and an optical phonon with a binding energy of the order of alpha omega(0), where alpha is the electron-phonon coupling and omega(0) the phonon energy. DOI: 10.1103/PhysRevLett.109.256602