BodlaenderMohring1993

https://www.doi.org/10.1137/0406014

@article{BodlaenderMohring1993,
author = {Hans L. Bodlaender and Rolf H. Möhring},
doi = {10.1137/0406014},
journaltitle = {SIAM Journal on Discrete Mathematics},
number = {2},
pages = {181--188},
title = {The Pathwidth and Treewidth of Cographs},
volume = {6},
year = {1993},
}

• page 4 : bounded complete does not imply bounded treewidth – Lemma 3.1 (“clique containment lemma”). Let $({X_i\mid u\in I},T=(I,F))$ be a tree-decomposition of $G=(V,E)$ and let $W \subseteq V$ be a clique in $G$. Then there exists $i \in I$ with $W \subseteq X_i$.
• page 4 : bounded bipartite does not imply bounded treewidth – Lemma 3.2 (“complete bipartite subgraph containment lemma”).