ganianTwinCover2015

@article{ganianTwinCover2015,
author = {Robert Ganian},
doi = {10.46298/dmtcs.2136},
journaltitle = {Discrete Mathematics \& Theoretical Computer Science},
month = {September},
title = {Improving Vertex Cover as a Graph Parameter},
volume = {{Vol. 17 no.2}},
year = {2015},
}

• page 5 : twin-cover number – Definition 3 A set of vertices $X \subseteq V(G)$ is a twin-cover of $G$ if for every edge $e = ab \in E(G)$ either 1. $a \in X$ or $b \in X$, or 2. $a$ and $b$ are true twins. We then say that $G$ has twin-cover $k$ if the size of a minimum twin-cover of $G$ is $k$.
• page 20 : twin-cover number upper bounds shrub-depth by a constant – Let $\mathcal H_k$ be the class of graphs of twin-cover $k$. Then $\mathcal H_k \subseteq \mathcal{TM}_{2^k+k}(2)$ and a tree-model of any $G \in \mathcal H_k$ may be constructed in single-exponential FPT time.