k-NLC graphs and polynomial algorithms by Wanke
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
be a positive integer. A \emph{ -node label controlled (NLC) graph} is a -NL graph defined as follows: … - page 4 : NLCT-width – Definition 2.2. Let
be a positive integer. A \emph{ -node label controlled (NLC) tree} is a -NL graph defined as follows: … - page 5 : graph class cograph has constant NLC-width – Fact 2.3.
is a -NLC graph if and only if is a co-graph. - page 6 : treewidth upper bounds NLC-width by an exponential function – Theorem 2.5. For each partial
-tree there is a -NLC tree with .