One of the possible catalyst deactivation mechanisms in the Fischer-Tropsch synthesis is carbon deposition in the form of a graphene overlayer. Currently no information is available on the nature of the interaction of these layers with the surface. The adsorption of graphene on the FCC-Co(111) surface was therefore studied. A chemical interaction between the graphene sheet and the cobalt surface was observed as evidenced by the partial DOS and Bader charge analysis. The adsorption energy was found to be small when normalized per carbon atom, but becoming large for extended graphene sheets. Graphene removal from the surface via lifting or sliding was considered. The energy barrier for sliding a graphene sheet is lower than the barrier for lifting, but the energy barriers become significant when placed into the context of realistic catalytic surfaces in the nanometer range.