Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover defined as: Given a graph G, a clique cover K of G and a non-negative integer k, does G have a vertex cover of size at most k +Σ CεK(|C| - 1)? We study the parameterized complexity hardness of this problem by a reduction from r-Partization. We then describe sequacious fixed-parameter tractability results for r-Partization, parameterized by the solution size k and the required chromaticity r, in perfect graphs and split graphs. For Odd Cycle Transversal, we describe an O*(2 k) algorithm for perfect graphs and a polynomial-time algorithm for co-chordal graphs. © 2012 Springer-Verlag.