Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
0answers
51 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 ...
13
votes
1answer
469 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
308 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
502 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
315 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 ...