On neighbourhood complexity and kernels for distance-r dominating sets on nowhere dense classes of graphs

Prelegent(ci)

Sebastian Siebertz

Afiliacja

Uniwersytet Warszawski

Termin

7 grudnia 2016 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

The r-neighbourhood complexity of a vertex set A from a graph G is the number of subsets of A which are induced as r-neighbourhoods of vertices of G. We prove that every sufficiently large set from a graph of a nowhere dense class has almost linear neighbourhood complexity. This provides us with a new characterisation of nowhere dense classes of graphs and with a powerful tool to prove the existence of almost linear kernels for distance-r dominating sets on these classes.

---