I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (graphs which can be built by the operations of disjoint union and complementation, starting from isolated vertices) have cliquewidth at most 2. (Courcelle et al, Upper bounds to the clique width of graphs). Now consider some fixed non-negative integer k, and consider the class of graphs $\mathcal{G} _k$ of graphs such that for every $G = (V,E) \in \mathcal{G} _k$ there is a set $S$ of at most k vertices such that $G[V - S]$ is a cograph. Since the graph class $\mathcal{G} _k$ can also be seen as the class of graphs that can be built out of cographs by adding at most $k$ vertices, this class has also been called cographs + $kv$.

My question is: what is a tight bound on the cliquewidth of graphs in $\mathcal{G}_k$?

It is known that if a graph $G$ is obtained from $H$ by deleting $k$ vertices then $cw(H) \leq 2^k (cw(G) + 1)$. This shows that if a cograph $G$ can be obtained from a graph $H$ by deleting $k$ vertices, then $cw(H) \leq 2^k (3 + 1)$, and hence the cliquewidth of a graph in $\mathcal{G}_k$ is at most $2^k 4$. I am unsure whether this exponential dependency on $k$ is necessary. In this context I would also be interested in the maximum decrease in the cliquewidth by deleting a vertex; i.e. if we delete a single vertex from a graph, how much can the cliquewidth decrease?


I think the exponential bound is necessary. Here is why.

Consider the disconnected graph $G$ on $n$ vertices, labelled $1$ to $n$. Denote the set of vertices that new vertex $i$ is connected to by $f(i)$, a subset of $\lbrace 1,2,\ldots,n \rbrace$. The question then becomes: is it possible to find such a function $f$ so that the set $\lbrace f(i) \mid 1 \le i \le k \rbrace$ of subsets of $V(G)$ generates a set of subsets of size $2^k$? With "generates" I mean the closure under the operation of taking pairwise subsets.

The idea here is that to distinguish between any subsets one needs to label them differently. However, due to the way the cliquewidth operations are restricted, this can only happen if their intersection is constructed first, and then the remaining vertices.

As far as I can tell, this scenario is possible, but clearly the above is quite far from a rigorous construction of an example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.