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

Revue Internationale avec comité de lecture : Journal Theoretical Computer Science, vol. 746, pp. 49-72, 2018

Auteurs: C. Picouleau , D. Paulusma , O. Diner , B. Ries

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.

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	=	746,
	pages	=	"49-72",
	note	=	"{AcceptÃ©}",
}