Refine my results

Contraction and deletion blockers for perfect graphs and H-free graphs

Y. Diner, Öznur ; Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Theoretical computer science, 2018, vol. 746, p. 49-72

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...