Skip to main content

Research Repository

Advanced Search

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

Diner, Ö.Y.; Paulusma, D.; Picouleau, C.; Ries, B.

Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs Thumbnail


Authors

Ö.Y. Diner

C. Picouleau

B. Ries



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.

Citation

Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science, 746, 49-72. https://doi.org/10.1016/j.tcs.2018.06.023

Journal Article Type Article
Acceptance Date Jun 12, 2018
Online Publication Date Jun 22, 2018
Publication Date Oct 25, 2018
Deposit Date Jun 26, 2018
Publicly Available Date Jun 22, 2019
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 746
Pages 49-72
DOI https://doi.org/10.1016/j.tcs.2018.06.023
Public URL https://durham-repository.worktribe.com/output/1328307

Files





You might also like



Downloadable Citations