clique-width

• 2022/09 Tran2022
  • page 25 : modular-width $k$ upper bounds clique-width by $\mathcal O(k)$ – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
  • page 25 : bounded clique-width does not imply bounded modular-width – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
  • page 36 : clique-width $k$ upper bounds twin-width by $2^{\mathcal O(k)}$ – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
  • page 36 : bounded twin-width does not imply bounded clique-width – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
• 2019 Sorge2019
  • page 9 : distance to cograph $k$ upper bounds clique-width by $2^{\mathcal O(k)}$ – Lemma 4.17. The distance $c$ to a cograph upper bounds the cliquewidth $q$. We have $q \le 2^{3+c}-1$.
• 2012 GanianTwinCover2012
  • page 263 : twin-cover number $k$ upper bounds clique-width by $\mathcal O(k)$ – The clique-width of graphs of twin-cover $k$ is at most $k+2$.
• 2006 Oum2006
  • 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
• 2005 Gurski2005
  • page 8 : clique-tree-width $k$ upper bounds clique-width by $\mathcal O(k)$
• 2000 courcelle2000
  • page 18 : treewidth $k$ upper bounds clique-width by $2^{\mathcal O(k)}$ – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
• 1998 Johansson1998
  • clique-width $k$ upper bounds NLC-width by $\mathcal O(k)$
  • NLC-width $k$ upper bounds clique-width by $\mathcal O(k)$
• unknown
  • distance to cograph $k$ upper bounds clique-width by $f(k)$
  • linear clique-width $k$ upper bounds clique-width by $f(k)$
  • clique-width $k$ upper bounds boolean width by $\mathcal O(k)$
  • boolean width $k$ upper bounds clique-width by $2^{\mathcal O(k)}$
  • modular-width $k$ upper bounds clique-width by $f(k)$
• SchroderThesis
  • page 16 : bounded clique cover number does not imply bounded clique-width – Proposition 3.9
  • page 23 : bounded genus does not imply bounded clique-width – Proposition 3.17
  • page 23 : bounded distance to planar does not imply bounded clique-width – Proposition 3.17
  • page 28 : bounded maximum degree does not imply bounded clique-width – Proposition 3.26
  • page 28 : bounded distance to bipartite does not imply bounded clique-width – Proposition 3.26
  • page 33 : bounded bisection bandwidth does not imply bounded clique-width – Proposition 3.32
• https://en.wikipedia.org/wiki/Clique-width
  • clique-width – … the minimum number of labels needed to construct G by means of the following 4 operations: 1. Creation of a new vertex… 2. Disjoint union of two labeled graphs… 3. Joining by an edge every vertex labeled $i$ to every vertex labeled $j$, where $i \ne j$ 4. Renaming label $i$ to label $j$