Paulusma, Daniël Picouleau, Christophe Ries, Bernard 2016 We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are NP-complete for general graphs even if d is fixed, we restrict the input graph G to some special graph class. We continue a line of research that considers these problems for subclasses of perfect graphs, but our main results are full classifications, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H. application/pdf https://folia.unifr.ch/global/documents/307828 https://folia.unifr.ch/documents/307828/files/blockers_rero_0.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-45587-7_4 info:eu-repo/semantics/openAccess License undefined Lecture Notes in Computer Science. - 2016, vol. 9849, p. 38-49 Clique number chromatic number edge contractions blocker vertex deletion forbidden induced subgraph info:eu-repo/classification/udc/004 Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions http://purl.org/coar/resource_type/c_6501