New Width Parameters of Graphs by Vatshelle

https://hdl.handle.net/1956/6166

@thesis{Vatshelle2012,
author = {Martin Vatshelle},
isbn = {978-82-308-2098-8},
publisher = {The University of Bergen},
title = {New Width Parameters of Graphs},
url = {https://hdl.handle.net/1956/6166},
year = {2012},
}

• page 33 : mim-width – Definition 3.7.1 (MIM-width). For $G$ a graph and $A \subseteq V(G)$ let $mim \colon 2^{V(G)} \to \mathbb N$ be a function where $mim(A)$ is the size of a maximum induced matching in $G[A,\bar A]$. Using Definition 3.1.3 with $f=mim$ we define $mimw(T,\delta$ as the $f$-width of a binary decomposition tree $(T,\delta)$ and $mimw(G)$ as the $f$-width of $G$, also called the MIM-width of $G$ or the maximum induced matching width.
• page 42 : boolean width upper bounds mim-width by a linear function – Theorem 4.2.10. Let $G$ be a graph, then $mimw(G) \le boolw(G) \le mimw(G) \log_2(n)$