linear clique-width

tags: linear variant

equivalent to: linear rank-width, linear clique-width, linear NLC-width

Relations

Results

• 2019 Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
  • shrub-depth upper bounds linear clique-width by a linear function – 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 Linear rank-width and linear clique-width of trees by Adler, Kanté
  • page 1 : linear rank-width upper bounds linear clique-width by a computable function – 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 upper bounds linear rank-width by a computable function – 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 Clique-Width is NP-Complete by Fellows, Rosamond, Rotics, Szeider
  • page 8 : pathwidth upper bounds linear clique-width by a linear function – (5) $\mathrm{lin-cwd}(G) \le \mathrm{pwd}(G)+2$.
• 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
  • page 5 : linear clique-width – Definition 6
  • page 8 : linear clique-width upper bounds clique-tree-width by a linear function
• 1998 Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
  • linear clique-width upper bounds linear NLC-width by a linear function
  • linear NLC-width upper bounds linear clique-width by a linear function
• unknown source
  • linear clique-width upper bounds clique-width by a computable function