rank-width

• 2023/02 Torunczyk2023
  • inf-flip-width $k$ upper bounds rank-width by $\mathcal O(k)$ – For every graph $G$, we have $\mathrm{rankwidth}(G) \le 3 \mathrm{fw}_\infty(G)+1$ …
  • rank-width $k$ upper bounds inf-flip-width by $2^{\mathcal O(k)}$ – For every graph $G$, we have … $3 \mathrm{fw}_\infty(G)+1 \le O(2^{\mathrm{rankwidth(G)}})$.
• 2012 GanianTwinCover2012
  • page 263 : twin-cover number $k$ upper bounds rank-width by $\mathcal O(k)$ – The rank-width and linaer rank-width of graph of twin-cover $k$ are at most $k+1$.
• 2011 BuiXuan2011
  • boolean width $k$ upper bounds rank-width by $2^{\mathcal O(k)}$ – \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 $k$ upper bounds boolean width by $k^{\mathcal O(1)}$ – \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 Jelinek2010
  • page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
• 2006 Oum2006
  • 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 $k$ implies that clique-width is $2^{\mathcal O(k)}$ – Proposition 6.3
  • page 9 : clique-width $k$ upper bounds rank-width by $\mathcal O(k)$ – Proposition 6.3
• unknown
  • linear rank-width $k$ upper bounds rank-width by $f(k)$
  • branch width $k$ upper bounds rank-width by $\mathcal O(k)$
• https://www.sciencedirect.com/science/article/pii/S0095895605001528
  • rank-width – see Section 6