A typical graph modification problem aims to modify a graph G, via a small number of operations from a specified set S, into some other graph H that has a certain desired property, which usually describes a certain graph class G to which H must belong. In this way a variety of classical graph-theoretic problems is captured. For instance, if only k vertex deletions are allowed and H must be an independent set or a clique, we obtain the Independent Set or Clique problem, respectively.

Now, instead of fixing a particular graph class G, we fix a certain graph parameter π. That is, given a graph G, a set S of one or more graph operations and an integer k, we ask whether G can be transformed into a graph G' by using at most k operations from S, such that π(G') ≤ π(G)-d for some threshold d ≥ 0. Such problems are called blocker problems, as the set of vertices or edges involved can be seen as ``blocking'' some desirable graph property (such as being colorable with only a few colors). Identifying the part of the graph responsible for a significant decrease of the parameter under consideration gives crucial information on the graph.

Blocker problems have been given much attention over the last few years. In this talk, I will give an overview of recent results on this topic.

When? | 04.12.2018 17:15 |
---|---|

Where? | PER 08 Phys 2.52 Chemin du Musée 3 1700 Fribourg |

Contact | Department of Mathematics isabella.schmutz@unifr.ch |