Contraction and deletion blockers for perfect graphs and H-free graphs
- Y. Diner, Öznur Kadir Has University
- Paulusma, Daniël Durham University
- Picouleau, Christophe CNAM
- Ries, Bernard University of Fribourg
-
2018
Published in:
- Theoretical computer science. - 2018, vol. 746, p. 49-72
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324496
- DOI 10.1016/j.tcs.2018.06.023
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307760
Statistics
Document views: 50
File downloads:
- blockers_rero.pdf: 157