# Questions tagged [cliquewidth]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
393 views

### Courcelle's theorem for bounded clique-width graphs

Courcelle's theorem states that "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded ...
153 views

### Number of k-expressions of graph (clique Width)

The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations. The Construction of a graph $G$ using the four operations is represented ...
159 views

### Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs

All $MSO_1$ and $MSO_2$ definable graph problems can be solved in linear time on bounded tree-width graphs by Courcelle's theorem. But it seems this theorem doesn't work for $MSO_2$ definable graph ...
222 views

### Clique-width expressions with logarithmic depth

When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...
759 views

### Modular Decomposition and Clique-width

I am trying to understand some concepts about Modular decomposition and Clique-width graphs. In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-...
539 views

### Is clique-width preserved under edge contractions?

Let $G$ be class of graphs with bounded clique-width. In each graph in $G$ some edges are contracted (e.g. randomly). Is now the clique-width still bounded? In case it is (in general) no longer ...