neighborhood diversity
abbr: nd
tags: module
equivalent to: neighborhood diversity
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | exclusion |
arboricity | exclusion | exclusion |
average degree | exclusion | exclusion |
average distance | exclusion | upper bound |
bandwidth | exclusion | exclusion |
bipartite | unbounded | exclusion |
bipartite number | exclusion | upper bound |
bisection bandwidth | exclusion | exclusion |
block | unbounded | exclusion |
book thickness | exclusion | exclusion |
boolean width | exclusion | upper bound |
bounded components | unknown to HOPS | exclusion |
boxicity | exclusion | upper bound |
branch width | exclusion | exclusion |
c-closure | exclusion | exclusion |
carving-width | exclusion | exclusion |
chordal | unbounded | exclusion |
chordality | exclusion | upper bound |
chromatic number | exclusion | exclusion |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | upper bound |
clique-width | exclusion | upper bound |
cluster | unknown to HOPS | exclusion |
co-cluster | unknown to HOPS | exclusion |
cograph | unknown to HOPS | exclusion |
complete | constant | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | exclusion | exclusion |
cycle | unbounded | exclusion |
cycles | unbounded | exclusion |
d-path-free | exclusion | exclusion |
degeneracy | exclusion | exclusion |
degree treewidth | exclusion | exclusion |
diameter | exclusion | upper bound |
diameter+max degree | unknown to HOPS | exclusion |
disjoint cycles | unbounded | exclusion |
distance to bipartite | exclusion | exclusion |
distance to block | exclusion | exclusion |
distance to bounded components | exclusion | exclusion |
distance to chordal | exclusion | exclusion |
distance to cluster | exclusion | exclusion |
distance to co-cluster | exclusion | exclusion |
distance to cograph | exclusion | exclusion |
distance to complete | upper bound | exclusion |
distance to edgeless | upper bound | exclusion |
distance to forest | exclusion | exclusion |
distance to interval | exclusion | exclusion |
distance to linear forest | exclusion | exclusion |
distance to maximum degree | exclusion | exclusion |
distance to outerplanar | exclusion | exclusion |
distance to perfect | exclusion | exclusion |
distance to planar | exclusion | unknown to HOPS |
distance to stars | unknown to HOPS | exclusion |
domatic number | exclusion | exclusion |
domination number | exclusion | exclusion |
edge clique cover number | upper bound | exclusion |
edge connectivity | exclusion | exclusion |
edgeless | constant | exclusion |
feedback edge set | exclusion | exclusion |
feedback vertex set | exclusion | exclusion |
forest | unbounded | exclusion |
genus | exclusion | exclusion |
girth | exclusion | upper bound |
grid | unbounded | exclusion |
h-index | exclusion | exclusion |
inf-flip-width | exclusion | upper bound |
interval | unbounded | exclusion |
iterated type partitions | exclusion | upper bound |
linear clique-width | exclusion | upper bound |
linear forest | unbounded | exclusion |
linear NLC-width | exclusion | upper bound |
linear rank-width | exclusion | upper bound |
maximum clique | exclusion | exclusion |
maximum degree | exclusion | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | unknown to HOPS |
maximum leaf number | exclusion | exclusion |
maximum matching | unknown to HOPS | exclusion |
maximum matching on bipartite graphs | upper bound | exclusion |
mim-width | exclusion | upper bound |
minimum degree | exclusion | exclusion |
mm-width | exclusion | exclusion |
modular-width | exclusion | upper bound |
module-width | exclusion | upper bound |
NLC-width | exclusion | upper bound |
NLCT-width | exclusion | upper bound |
odd cycle transversal | exclusion | exclusion |
outerplanar | unbounded | exclusion |
path | unbounded | exclusion |
pathwidth | exclusion | exclusion |
pathwidth+maxdegree | exclusion | exclusion |
perfect | unbounded | exclusion |
planar | unbounded | exclusion |
radius-r flip-width | exclusion | upper bound |
rank-width | exclusion | upper bound |
shrub-depth | exclusion | upper bound |
sim-width | exclusion | upper bound |
star | constant | exclusion |
stars | unknown to HOPS | exclusion |
topological bandwidth | exclusion | exclusion |
tree | unbounded | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | exclusion |
treelength | exclusion | upper bound |
treewidth | exclusion | exclusion |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | upper bound |
vertex connectivity | unknown to HOPS | exclusion |
vertex cover | upper bound | exclusion |
vertex integrity | exclusion | exclusion |
Results
- 2024 Parameterized complexity for iterated type partitions and modular-width by Cordasco, Gargano, Rescigno
- page 3 : neighborhood diversity upper bounds iterated type partitions by a linear function – … $itp(G) \le nd(G)$. Actually $itp(G)$ can be arbitrarily smaller than $nd(G)$.
- page 3 : bounded iterated type partitions does not imply bounded neighborhood diversity – … $itp(G) \le nd(G)$. Actually $itp(G)$ can be arbitrarily smaller than $nd(G)$.
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- 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 22 : edge clique cover number upper bounds neighborhood diversity by an exponential function – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
- page 22 : bounded neighborhood diversity does not imply bounded edge clique cover number – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
- page 23 : vertex cover upper bounds neighborhood diversity by an exponential function – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
- 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 upper bounds boxicity by a polynomial function – 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.
- 2019 Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
- 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$.
- 2013 Parameterized Algorithms for Modular-Width by Gajarský, Lampis, Ordyniak
- page 6 : neighborhood diversity upper bounds modular-width by a linear function – 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, …
- https://link.springer.com/article/10.1007/s00453-011-9554-x
- 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.
- https://www.fi.muni.cz/~hlineny/papers/shrubdepth-warw18-slipp.pdf
- page 9 : neighborhood diversity upper bounds shrub-depth by a constant – Shrub-depth 1: e.g., cliques, stars, \dots, gen. BND – bounded neighborhood diversity.
- unknown source
- edge clique cover number upper bounds neighborhood diversity by an exponential function – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
- vertex cover upper bounds neighborhood diversity by an exponential function
- bounded twin-cover number does not imply bounded neighborhood diversity
- bounded vertex integrity does not imply bounded neighborhood diversity