Wanke1994

https://www.doi.org/10.1016/0166-218X(94)90026-4

@article{Wanke1994,
author = {Egon Wanke},
doi = {10.1016/0166-218X(94)90026-4},
issn = {0166-218X},
journaltitle = {Discrete Applied Mathematics},
number = {2},
pages = {251--266},
title = {k-NLC graphs and polynomial algorithms},
volume = {54},
year = {1994},
}

• page 3 : NLC-width – Definition 2.1. Let $k \in \mathbb N$ be a positive integer. A \emph{$k$-node label controlled (NLC) graph} is a $k$-NL graph defined as follows: …
• page 4 : NLCT-width – Definition 2.2. Let $k \in \mathbb N$ be a positive integer. A \emph{$k$-node label controlled (NLC) tree} is a $k$-NL graph defined as follows: …
• page 5 : cograph upper bounds NLC-width by a constant – Fact 2.3. $G$ is a $1$-NLC graph if and only if $unlab(G)$ is a co-graph.
• page 6 : treewidth $k$ upper bounds NLC-width by $2^{\mathcal O(k)}$ – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.