Algorithmic Meta-theorems for Restrictions of Treewidth by Lampis

https://www.doi.org/10.1007/s00453-011-9554-x

@article{lampis2012,
author = {Michael Lampis},
day = {1},
doi = {10.1007/s00453-011-9554-x},
issue = {1},
journaltitle = {Algorithmica},
month = {September},
pages = {19--37},
series = {1432-0541},
title = {Algorithmic Meta-theorems for Restrictions of Treewidth},
volume = {64},
year = {2012},
}

• neighborhood diversity – We will say that two vertices $v, v’$ of a graph $G(V, E)$ have the same type iff they have the same colors and $N(v) \setminus {v}=N(v’) \setminus {v}$, where $N(v)$ denotes the set of neighbors of $v$. … A colored graph $G(V, E)$ has neighborhood diversity at most $w$, if there exists a partition of $V$ into at most $w$ sets, such that all the vertices in each set have the same type.