Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Diner, Öznur Yaşar and Paulusma, Daniël and Picouleau, Christophe and Ries, Bernard (2018) 'Contraction and deletion blockers for perfect graphs and H -free graphs.', Theoretical computer science., 746 . pp. 49-72.

Abstract

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 for S={ec}S={ec} and S={vd}S={vd} and π∈{χ,ω,α}π∈{χ,ω,α} for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S={ec}S={ec} and S={vd}S={vd} and π∈{χ,ω,α}π∈{χ,ω,α} restricted to H-free graphs.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(523Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2018.06.023
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:12 June 2018
Date deposited:26 June 2018
Date of first online publication:22 June 2018
Date first made open access:22 June 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar