linear clique-width

• 2019/01 Ganian2019
  • shrub-depth $k$ upper bounds linear clique-width by $\mathcal O(k)$ – Proposition 3.4. Let $\mathcal G$ be a graph class and $d$ an integer. Then: … b) If $\mathcal G$ is of bounded shrub-depth, then $\mathcal G$ is of bounded linear clique-width.
• 2015 Adler2015
  • page 1 : linear rank-width $k$ upper bounds linear clique-width by $f(k)$ – Linear rank-width is equivalent to linear clique-width in the sense that any graph class has bounded linear clique-width if and only if it has bounded linear rank-width.
  • page 1 : linear clique-width $k$ upper bounds linear rank-width by $f(k)$ – Linear rank-width is equivalent to linear clique-width in the sense that any graph class has bounded linear clique-width if and only if it has bounded linear rank-width.
• 2009 cliquewidthnpc2009
  • page 8 : pathwidth $k$ upper bounds linear clique-width by $\mathcal O(k)$ – (5) $\mathrm{lin-cwd}(G) \le \mathrm{pwd}(G)+2$.
• 2005 Gurski2005
  • page 5 : linear clique-width – Definition 6
  • page 8 : linear clique-width $k$ upper bounds clique-tree-width by $\mathcal O(k)$
• 1998 Johansson1998
  • linear clique-width $k$ upper bounds linear NLC-width by $\mathcal O(k)$
  • linear NLC-width $k$ upper bounds linear clique-width by $\mathcal O(k)$
• unknown
  • linear clique-width $k$ upper bounds clique-width by $f(k)$