page 14 : neighborhood diversity – The neighborhood diversity $nd(G)$ of a graph $G$ is the smallest number $k$ such that there is a $k$-partition $(V_1,\dots,V_k)$ of $G$, where each subset $V_i$, $i \in [k]$ is a module and is either a complete set or an independent set.
page 23 : bounded neighborhood diversity does not imply bounded vertex cover – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
page 26 : graph class path has unbounded neighborhood diversity – The Neighborhood Diversity of a Path $P$ with length $n > 3$ is $n$.
page 26 : neighborhood diversity $k$ upper bounds boxicity by $k^{\mathcal O(1)}$ – Note that given a path of length $n > 3$. The boxicity is 1 while … neighborhood diversity is $n$. … a graph … with neighborhood diversity of $k$, its boxicity is at most $k+k^2$.
page 26 : bounded boxicity does not imply bounded neighborhood diversity – Note that given a path of length $n > 3$. The boxicity is 1 while … neighborhood diversity is $n$. … a graph … with neighborhood diversity of $k$, its boxicity is at most $k+k^2$.
page 28 : bounded neighborhood diversity does not imply bounded twin-cover number – Proposition 4.12. Modular-width is incomparable to Distance to Twin Cover Number.
page 28 : bounded twin-cover number does not imply bounded neighborhood diversity – Proposition 4.12. Modular-width is incomparable to Distance to Twin Cover Number.
neighborhood diversity upper bounds shrub-depth by a constant – $\mathcal{TM}_m(1)$ is exactly the class of graphs of neighborhood diversity at most $m$.
page 6 : neighborhood diversity $k$ upper bounds modular-width by $\mathcal O(k)$ – Theorem 3. Let $G$ be a graph. Then $\mathrm{mw}(G) \le \mathrm{nd}(G)$ and $\mathrm{mw}(G) \le 2\mathrm{tc}(G) + \mathrm{tc}(G)$. Furthermore, both inequalities are strict, …
page 6 : bounded modular-width does not imply bounded neighborhood diversity – Theorem 3. Let $G$ be a graph. Then $\mathrm{mw}(G) \le \mathrm{nd}(G)$ and $\mathrm{mw}(G) \le 2\mathrm{tc}(G) + \mathrm{tc}(G)$. Furthermore, both inequalities are strict, …
edge clique cover number $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
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.
