Generalized Above Guarantee Vertex Cover and r-Partization

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

$\cal K$

of

G

and a non-negative integer

k

, does

G

have a vertex cover of size at most

$k+\sum_{C \in \cal 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.