Contraction and Deletion Blockers for Perfect Graphs and H-Free Graphs

Abstract

We study the following problem: for given integers d k and graph G can we reduce some fixed graph parameter pi of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number chi clique number omega and independence number alpha 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 pi is an element of{chi omega alpha} 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 pi is an element of{chi omega alpha} restricted to H-free graphs. (C) 2018 Elsevier B.V. All rights reserved.