Y. Diner, Öznur Paulusma, Daniël Picouleau, Christophe Ries, Bernard 2018 We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S={ec} and S={vd} and π∈{χ, ω, α} for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S={ec} and S={vd} and π∈{χ, ω, α} restricted to H-free graphs. application/pdf https://folia.unifr.ch/global/documents/307760 https://folia.unifr.ch/documents/307760/files/blockers_rero.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2018.06.023 info:eu-repo/semantics/openAccess License undefined Theoretical computer science. - 2018, vol. 746, p. 49-72 Contraction blockers Deletion blockers Complexity Perfect graphs H-free graphs info:eu-repo/classification/udc/33 Contraction and deletion blockers for perfect graphs and H-free graphs http://purl.org/coar/resource_type/c_6501