Browsing by Author "Paulusma, Daniel"
Now showing items 1-2 of 2
-
Contraction and deletion blockers for perfect graphs and H-free graphs
Authors:Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard
Publisher and Date:(Elsevier Science, 2018)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 ...
-
Contraction Blockers for Graphs with Forbidden Induced Paths
Authors:Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard
Publisher and Date:(Springer-Verlag Berlin, 2015)We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number clique number and independence number. For each of these graph parameters we show that when d is part of the input this problem is polynomial-time solvable on P-4-free graphs and NP-complete as well as W[1]-hard with parameter d for split graphs. As split ...