Advanced Search

Refine my results

Document type

Institution

Specific Collection

Language

Author

Domain

Keyword

Sorted by: Date of deposit
2 results 1
Université de Fribourg

Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Lecture Notes in Computer Science, 2016, vol. 9849, p. 38-49

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are...

Université de Fribourg

Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions

Paulusma, Daniël ; Picouleau, Christophe ; Ries, Bernard

In: Lecture Notes in Computer Science, 2017, vol. 10185, p. 470-483

Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these...

2 results 1