rank-width
equivalent to: rank-width, boolean width, inf-flip-width, clique-width, NLC-width, module-width
providers: ISGCI
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 | tight bounds |
cluster | constant | exclusion |
co-cluster | constant | exclusion |
cograph | constant | exclusion |
complete | constant | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | upper bound | exclusion |
cycle | constant | exclusion |
cycles | constant | exclusion |
d-path-free | upper bound | exclusion |
degeneracy | exclusion | exclusion |
degree treewidth | upper bound | exclusion |
diameter | exclusion | exclusion |
diameter+max degree | upper bound | exclusion |
disjoint cycles | constant | 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 | unknown to HOPS | exclusion |
distance to co-cluster | upper bound | exclusion |
distance to cograph | upper bound | exclusion |
distance to complete | upper bound | 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 | constant | exclusion |
feedback edge set | upper bound | exclusion |
feedback vertex set | upper bound | exclusion |
forest | constant | 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 | constant | 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 | unknown to HOPS | 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 | upper bound | upper bound |
NLCT-width | upper bound | unknown to HOPS |
odd cycle transversal | exclusion | exclusion |
outerplanar | constant | exclusion |
path | constant | exclusion |
pathwidth | upper bound | exclusion |
pathwidth+maxdegree | upper bound | exclusion |
perfect | unbounded | exclusion |
planar | unbounded | exclusion |
radius-r flip-width | exclusion | upper bound |
shrub-depth | upper bound | exclusion |
sim-width | unknown to HOPS | upper bound |
star | constant | exclusion |
stars | constant | exclusion |
topological bandwidth | upper bound | exclusion |
tree | constant | 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 | unknown to HOPS | exclusion |
vertex cover | upper bound | exclusion |
vertex integrity | upper bound | exclusion |
Results
- 2023 Flip-width: Cops and Robber on dense graphs by Toruńczyk
- inf-flip-width upper bounds rank-width by a linear function – For every graph $G$, we have $\mathrm{rankwidth}(G) \le 3 \mathrm{fw}_\infty(G)+1$ …
- rank-width upper bounds inf-flip-width by an exponential function – For every graph $G$, we have … $3 \mathrm{fw}_\infty(G)+1 \le O(2^{\mathrm{rankwidth(G)}})$.
- 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
- page 263 : twin-cover number upper bounds rank-width by a linear function – The rank-width and linaer rank-width of graph of twin-cover $k$ are at most $k+1$.
- 2011 Boolean-width of graphs by Bui-Xuan, Telle, Vatshelle
- boolean width upper bounds rank-width by an exponential function – \textbf{Corollary 1.} For any graph $G$ and decomposition tree $(T,\gamma)$ of $G$ it holds that … $\log_2 rw(G) \le boolw(G)$ …
- rank-width upper bounds boolean width by a polynomial function – \textbf{Corollary 1.} For any graph $G$ and decomposition tree $(T,\gamma)$ of $G$ it holds that … $boolw(G) \le \frac 14 rw^2(G)+O(rw(G))$.
- 2010 The rank-width of the square grid by Jelínek
- page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
- 2006 Approximating clique-width and branch-width by Oum, Seymour
- page 9 : rank-width – … and the \emph{rank-width} $\mathrm{rwd}(G)$ of $G$ is the branch-width of $\mathrm{cutrk}_G$.
- page 9 : rank-width upper and lower bounds clique-width by an exponential function – Proposition 6.3
- page 9 : clique-width upper bounds rank-width by a linear function – Proposition 6.3
- https://www.sciencedirect.com/science/article/pii/S0095895605001528
- rank-width – see Section 6
- unknown source
- linear rank-width upper bounds rank-width by a computable function
- branch width upper bounds rank-width by a linear function