Diner, Öznur YaşarPaulusma, DanielPicouleau, ChristopheRies, Bernard2019-06-272019-06-2720159978-3-319-18173-8978-3-319-18172-10302-97431611-33490302-97431611-3349https://hdl.handle.net/20.500.12469/647https://doi.org/10.1007/978-3-319-18173-8_14We 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 graphs form a subclass of P-5-free graphs both results together give a complete complexity classification for P-l-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show on the positive side that the problem is polynomial-time solvable for each parameter on split graphs if d is fixed i.e. not part of the input. We also initiate a study into other subclasses of perfect graphs namely cobipartite graphs and interval graphs.eninfo:eu-repo/semantics/openAccessConference Object1942079079WOS:00036201670001510.1007/978-3-319-18173-8_142-s2.0-84944728432N/AQ2