Faculté des sciences économiques et sociales
Public access from 22-giu-2020

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

Y. Diner, Öznur ; Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Theoretical computer science, 2018, vol. 746, p. 49-72

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... Di più

Aggiungi alla tua lista
    Summary
    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} and 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} and S={vd} and π∈{χ, ω, α} restricted to H-free graphs.