Rechercher

[PPD18] Contraction and Deletion Blockers for Perfect Graphs and H-free Graphs

Revue Internationale avec comité de lecture : Journal Theoretical Computer Science, vol. Accepté, pp. 00-00, 2018
motcle:
Résumé: We study the following problem: for given integers d, k and grap G, can we reduce some fixed graph parameter \pi 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 and vertex deletion . We determine the complexity of this problem for a number of subclasses of perfect graphs.

Commentaires: Accepté

BibTeX

@article {
PPD18,
title="{Contraction and Deletion Blockers for Perfect Graphs and H-free Graphs}",
author="C. Picouleau and D. Paulusma and O. Diner and B. ries",
journal="Theoretical Computer Science",
year=2018,
volume=Accepté,
pages="00-00",
note="{Accepté}",
}