modular-width

tags: module

equivalent to: modular-width

Relations

Results

• 2024 Parameterized complexity for iterated type partitions and modular-width by Cordasco, Gargano, Rescigno
  • page 3 : iterated type partitions upper bounds modular-width by a linear function – By definition
• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • page 14 : modular-width – The modular-width $mw(G)$ of a graph $G$ is the smallest number $h$ such that a $k$-partition $(V_1,\dots,V_k)$ of $G$ exists, where $k \le h$ and each subset $V_i$, $i \in [k]$ is a module and either contains a single vertex or for which the modular-subgraph $G[V_i]$ has a modular-width of $h$.
  • page 24 : graph class path has unbounded modular-width – The Modular-width of a path $P$ with length $n > 3$ is $n$.
  • page 25 : modular-width upper bounds clique-width by a linear function – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
  • page 25 : bounded clique-width does not imply bounded modular-width – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
  • page 25 : modular-width upper bounds diameter by a linear function – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
  • page 25 : bounded diameter does not imply bounded modular-width – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
  • page 28 : bounded modular-width does not imply bounded distance to cluster – Proposition 4.10. Modular-width is incomparable to Distance to Cluster.
  • page 28 : bounded distance to cluster does not imply bounded modular-width – Proposition 4.10. Modular-width is incomparable to Distance to Cluster.
  • page 28 : bounded modular-width does not imply bounded distance to co-cluster – Proposition 4.11. Modular-width is incomparable to Distance to Co-Cluster.
  • page 28 : bounded distance to co-cluster does not imply bounded modular-width – Proposition 4.11. Modular-width is incomparable to Distance to Co-Cluster.
  • page 30 : bounded modular-width does not imply bounded chordality – Theorem 4.16. Modular-width is incomparable to Chordality.
  • page 30 : bounded chordality does not imply bounded modular-width – Theorem 4.16. Modular-width is incomparable to Chordality.
• 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, …
  • page 6 : twin-cover number upper bounds modular-width by an exponential 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 twin-cover number – 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 8 : bounded modular-width does not imply bounded shrub-depth – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
  • page 8 : bounded shrub-depth does not imply bounded modular-width – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
• unknown source
  • modular-width upper bounds clique-width by a computable function
  • modular-width upper bounds diameter by a computable function