Cliquewidth of Almost Cographs

Question

(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 (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$, i.e. the graphs which can be turned into a cograph by deleting k vertices?

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 $4*2^k$. 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?

Answer 1

I will try to answer this old question of yours, although I am not sure my answer is conclusive but it should point you in the right direction.

First let us discuss linear clique-width. If a graph has linear clique-width $k$, and one add $1$ vertex to the graph, that vertex can always be placed first in the ordering with a unique color. Hence linear clique-width only increases by at most 1 when you add a vertex.

Gurski and Wanke showed in "On the relationship between NLC-width and linear NLC-width" that cographs have unbounded linear clique-width.

Since cographs have unbounded linear clique-width but bounded clique-width any good clique decomposition must have a tree structure. We must show that we can force arbitrarily many deep branches. Now we do as we do for trees, construct a tree with at 2^k leaves add k vertices and each leaf is connected to a unique subset of new vertices.