rank-width

• Torunczyk2023
  • 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)}})$.
• 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 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
• Jelinek2010
  • page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
• unknown source
  • linear rank-width upper bounds rank-width by a computable function
  • branch width upper bounds rank-width by a linear function
• https://www.sciencedirect.com/science/article/pii/S0095895605001528
  • rank-width – see Section 6
• GanianTwinCover2012
  • 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$.
• BuiXuan2011
  • 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))$.