clique-width

abbr: cw

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

providers: ISGCI

Relations

Results

• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • 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.
• 2019 The Graph Parameter Hierarchy by Sorge
  • 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$.
• 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
  • 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$.
• 2006 Approximating clique-width and branch-width by Oum, Seymour
  • 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
• 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
  • page 8 : clique-tree-width upper bounds clique-width by a linear function
• 2000 Upper bounds to the clique width of graphs by Courcelle, Olariu
  • 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$ …
• 1998 Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
  • clique-width upper bounds NLC-width by a linear function
  • NLC-width upper bounds clique-width by a linear function
• unknown source
  • 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
  • module-width upper bounds clique-width by a computable function
  • clique-width upper bounds module-width by a computable function
  • modular-width upper bounds clique-width by a computable function
  • clique-width upper bounds mim-width by a computable function
  • clique-width upper bounds twin-width by a computable function
• 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$
• Comparing Graph Parameters by Schröder
  • 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