NLC-width

• 2005 Gurski2005
  • page 8 : NLCT-width $k$ upper bounds NLC-width by $\mathcal O(k)$
• 1998 Johansson1998
  • clique-width $k$ upper bounds NLC-width by $\mathcal O(k)$
  • NLC-width $k$ upper bounds clique-width by $\mathcal O(k)$
• 1994 Wanke1994
  • 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 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)$.