We propose a class of cooperative games, called PARTITIONED COMBINATORIAL OPTIMIZATION GAMEs (PCOGs). The input of PCOG consists of a set of agents and a combinatorial structure (typically a graph) with a fixed optimization goal on this structure (e.g., finding a minimum dominating set on a graph) such that the structure is divided among the agents. The value of each coalition of agents is derived from the optimal solution for the part of the structure possessed by the coalition. We study two fundamental questions related to the core: CORE STABILITY VERIFICATION and CORE STABILITY EXISTENCE. We analyze the algorithmic complexity of both questions for four classic graph optimization tasks: minimum vertex cover, minimum dominating set, minimum spanning tree, and maximum matching.