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

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

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