The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
35 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 ...
11
votes
1answer
86 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 ...
14
votes
1answer
475 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 ...
10
votes
2answers
311 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, ...
13
votes
2answers
505 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 ...
23
votes
1answer
316 views

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs ...