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

Speaker(s)

Sebastian Siebertz

Affiliation

Uniwersytet Warszawski

Date

Dec. 7, 2016, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---