The interplay of electron-phonon (el-ph) and electron-electron (el-el) interactions in epitaxial graphene is studied by directly probing its electronic structure. We found a strong coupling of electrons to the soft part of the A1g phonon evident by a kink at 150+/-15 meV, while the coupling of electrons to another expected phonon E2g at 195 meV can only be barely detected. The possible role of the el-el interaction to account for the enhanced coupling of electrons to the A1g phonon, and the contribution of el-ph interaction to the linear imaginary part of the self energy at high binding energy are also discussed. Our results reveal the dominant role of the A1g phonon in the el-ph interaction in graphene, and highlight the important interplay of el-el and el-ph interactions in the self energy of graphene.