clique-width

• 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
• Oum2006
  • 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
• Gurski2005
  • page 8 : clique-tree-width upper bounds clique-width by a linear function
• GanianTwinCover2012
  • page 263 : twin-cover number upper bounds clique-width by a linear function – The clique-width of graphs of twin-cover $k$ is at most $k+2$.
• unknown source
  • distance to cograph upper bounds clique-width by a computable function
  • linear clique-width upper bounds clique-width by a computable function
  • clique-width upper bounds boolean width by a linear function
  • boolean width upper bounds clique-width by an exponential function
  • modular-width upper bounds clique-width by a computable function
• Sorge2019
  • page 9 : distance to cograph upper bounds clique-width by an exponential function – Lemma 4.17. The distance $c$ to a cograph upper bounds the cliquewidth $q$. We have $q \le 2^{3+c}-1$.
• 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$
• courcelle2000
  • page 18 : treewidth upper bounds clique-width by an exponential function – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
• Tran2022
  • page 25 : modular-width upper bounds clique-width by a linear function – 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 upper bounds twin-width by an exponential function – 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.
• Johansson1998
  • clique-width upper bounds NLC-width by a linear function
  • NLC-width upper bounds clique-width by a linear function