# Questions tagged [cliquewidth]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
162 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 ...
404 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 ...
166 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 ...
243 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 ...
796 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-...
461 views

### MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, ...
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 ...