Contraction and deletion blockers for perfect graphs and H-free graphs
Loading...
Date
2018
Authors
Diner, Öznur Yaşar
Paulusma, Daniel
Picouleau, Christophe
Ries, Bernard
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier Science
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.
Description
Keywords
Contraction blockers, Deletion blockers, Complexity, Perfect graphs, H-free graphs
Turkish CoHE Thesis Center URL
Citation
10
WoS Q
N/A
Scopus Q
Q2
Source
Volume
746
Issue
Start Page
49
End Page
72