(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?
Cliquewidth of Almost Cographs
graph theory;co.combinatorics;cliquewidth