rank-width

equivalent to: clique-width, boolean width, NLC-width, inf-flip-width, module-width

providers: ISGCI

Relations

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 constant – 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
• assumed
  • rank-width is equivalent to rank-width – assumed
• unknown source
  • linear rank-width upper bounds rank-width by a computable function
  • branch width upper bounds rank-width by a linear function