# Cliquewidth of Cographs + kv

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?

-

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.