modularwidth2013

https://www.doi.org/10.1007/978-3-319-03898-8_15

@inproceedings{modularwidth2013,
location = {Cham},
author = {Jakub Gajarsk{ý} and Michael Lampis and Sebastian Ordyniak},
booktitle = {Parameterized and Exact Computation},
doi = {10.1007/978-3-319-03898-8_15},
editor = {Gutin, Gregory and Szeider, Stefan},
isbn = {978-3-319-03898-8},
pages = {163--176},
publisher = {Springer International Publishing},
title = {Parameterized Algorithms for Modular-Width},
year = {2013},
}

• 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, …
• page 6 : twin-cover number $k$ upper bounds modular-width by $2^{\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 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.