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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
(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 ...