NLC-width
equivalent to: clique-width, boolean width, inf-flip-width, rank-width, module-width
Relations
Other | Relation from | Relation to | |
---|---|---|---|
acyclic chromatic number | ■ | exclusion | exclusion |
arboricity | ■ | exclusion | exclusion |
average degree | ■ | exclusion | exclusion |
average distance | ■ | exclusion | exclusion |
bandwidth | ■ | upper bound | exclusion |
bipartite | ■ | unbounded | exclusion |
bipartite number | ■ | exclusion | unknown to HOPS |
bisection bandwidth | ■ | exclusion | exclusion |
block | ■ | unknown to HOPS | exclusion |
book thickness | ■ | exclusion | exclusion |
boolean width | ■ | upper bound | upper bound |
bounded components | ■ | upper bound | exclusion |
boxicity | ■ | exclusion | exclusion |
branch width | ■ | upper bound | exclusion |
c-closure | ■ | exclusion | exclusion |
carving-width | ■ | upper bound | exclusion |
chordal | ■ | unknown to HOPS | exclusion |
chordality | ■ | exclusion | exclusion |
chromatic number | ■ | exclusion | exclusion |
clique cover number | ■ | exclusion | exclusion |
clique-tree-width | ■ | upper bound | unknown to HOPS |
clique-width | ■ | upper bound | upper bound |
cluster | ■ | upper bound | exclusion |
co-cluster | ■ | upper bound | exclusion |
cograph | ■ | upper bound | exclusion |
complete | ■ | upper bound | exclusion |
connected | ■ | unbounded | exclusion |
contraction complexity | ■ | upper bound | exclusion |
cutwidth | ■ | upper bound | exclusion |
cycle | ■ | upper bound | exclusion |
cycles | ■ | upper bound | exclusion |
d-path-free | ■ | upper bound | exclusion |
degeneracy | ■ | exclusion | exclusion |
degree treewidth | ■ | upper bound | exclusion |
diameter | ■ | exclusion | exclusion |
diameter+max degree | ■ | upper bound | exclusion |
disconnected | ■ | unknown to HOPS | exclusion |
disjoint cycles | ■ | upper bound | exclusion |
distance to bipartite | ■ | exclusion | exclusion |
distance to block | ■ | unknown to HOPS | exclusion |
distance to bounded components | ■ | upper bound | exclusion |
distance to chordal | ■ | exclusion | exclusion |
distance to cluster | ■ | upper bound | exclusion |
distance to co-cluster | ■ | upper bound | exclusion |
distance to cograph | ■ | upper bound | exclusion |
distance to complete | ■ | upper bound | exclusion |
distance to disconnected | ■ | exclusion | exclusion |
distance to edgeless | ■ | upper bound | exclusion |
distance to forest | ■ | upper bound | exclusion |
distance to interval | ■ | exclusion | exclusion |
distance to linear forest | ■ | upper bound | exclusion |
distance to maximum degree | ■ | exclusion | exclusion |
distance to outerplanar | ■ | upper bound | exclusion |
distance to perfect | ■ | exclusion | exclusion |
distance to planar | ■ | exclusion | exclusion |
distance to stars | ■ | upper bound | exclusion |
domatic number | ■ | exclusion | exclusion |
domination number | ■ | exclusion | exclusion |
edge clique cover number | ■ | upper bound | exclusion |
edge connectivity | ■ | exclusion | exclusion |
edgeless | ■ | upper bound | exclusion |
feedback edge set | ■ | upper bound | exclusion |
feedback vertex set | ■ | upper bound | exclusion |
forest | ■ | upper bound | exclusion |
genus | ■ | exclusion | exclusion |
girth | ■ | exclusion | exclusion |
grid | ■ | unbounded | exclusion |
h-index | ■ | exclusion | exclusion |
inf-flip-width | ■ | upper bound | upper bound |
interval | ■ | unknown to HOPS | exclusion |
iterated type partitions | ■ | upper bound | exclusion |
linear clique-width | ■ | upper bound | unknown to HOPS |
linear forest | ■ | upper bound | exclusion |
linear NLC-width | ■ | upper bound | unknown to HOPS |
linear rank-width | ■ | upper bound | unknown to HOPS |
maximum clique | ■ | exclusion | exclusion |
maximum degree | ■ | exclusion | exclusion |
maximum independent set | ■ | exclusion | exclusion |
maximum induced matching | ■ | exclusion | exclusion |
maximum leaf number | ■ | upper bound | exclusion |
maximum matching | ■ | upper bound | exclusion |
maximum matching on bipartite graphs | ■ | upper bound | exclusion |
mim-width | ■ | unknown to HOPS | upper bound |
minimum degree | ■ | exclusion | exclusion |
mm-width | ■ | upper bound | exclusion |
modular-width | ■ | upper bound | exclusion |
module-width | ■ | upper bound | upper bound |
neighborhood diversity | ■ | upper bound | exclusion |
NLC-width | ■ | equal | equal |
NLCT-width | ■ | upper bound | unknown to HOPS |
odd cycle transversal | ■ | exclusion | exclusion |
outerplanar | ■ | upper bound | exclusion |
path | ■ | upper bound | exclusion |
pathwidth | ■ | upper bound | exclusion |
pathwidth+maxdegree | ■ | upper bound | exclusion |
perfect | ■ | unbounded | exclusion |
planar | ■ | unbounded | exclusion |
radius-r flip-width | ■ | exclusion | upper bound |
rank-width | ■ | upper bound | upper bound |
shrub-depth | ■ | upper bound | exclusion |
sim-width | ■ | unknown to HOPS | upper bound |
size | ■ | upper bound | exclusion |
star | ■ | upper bound | exclusion |
stars | ■ | upper bound | exclusion |
topological bandwidth | ■ | upper bound | exclusion |
tree | ■ | upper bound | exclusion |
tree-independence number | ■ | unknown to HOPS | unknown to HOPS |
treedepth | ■ | upper bound | exclusion |
treelength | ■ | exclusion | unknown to HOPS |
treewidth | ■ | upper bound | exclusion |
twin-cover number | ■ | upper bound | exclusion |
twin-width | ■ | exclusion | upper bound |
vertex connectivity | ■ | exclusion | exclusion |
vertex cover | ■ | upper bound | exclusion |
vertex integrity | ■ | upper bound | exclusion |
Results
- 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
- page 8 : NLCT-width upper bounds NLC-width by a linear function
- 1998 Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
- clique-width upper bounds NLC-width by a linear function
- NLC-width upper bounds clique-width by a linear function
- 1994 k-NLC graphs and polynomial algorithms by Wanke
- 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 upper bounds NLC-width by an exponential function – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.
- assumed