Cliquewidth of Casi Cographs

( Publiqué esta pregunta en MathOverflow hace dos semanas, pero hasta ahora sin una respuesta rigurosa)

Tengo una pregunta sobre las medidas de ancho de gráficos de gráficos simples no dirigidos. Es bien sabido que los cográficos (gráficos que pueden construirse mediante las operaciones de unión y complementación disjuntas, comenzando por vértices aislados) tienen un ancho de camarilla como máximo 2. (Courcelle et al, límites superiores al ancho de camarilla de los gráficos). Ahora considere algunos enteros no negativos fijos k, y considere la clase de gráficos de gráficos tales que para cada hay un conjunto de at la mayoría de los vértices k tal que es un cograma. Dado que la clase de gráfico también se puede ver como la clase de gráficos que se pueden construir a partir de los cogramas agregando como máximo$\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$$\mathcal{G} _k$$k$vértices, esta clase también se ha llamado cografías + .$kv$

Mi pregunta es: ¿cuál es un límite estrecho en el ancho de camarilla de los gráficos en , es decir, los gráficos que se pueden convertir en un cograma eliminando k vértices?$\mathcal{G}_k$

Se sabe que si se obtiene un gráfico de eliminando vértices, entonces . Esto muestra que si se puede obtener una cografía de un gráfico eliminando vértices, entonces , y por lo tanto, el ancho de la camarilla de un gráfico en es a lo sumo . No estoy seguro de si esta dependencia exponencial de es necesaria. En este contexto, también estaría interesado en la disminución máxima en el ancho de la camarilla eliminando un vértice; es decir, si eliminamos un solo vértice de un gráfico, ¿cuánto puede disminuir el ancho de la camarilla?$G$$H$$k$$cw(H) \leq 2^k (cw(G) + 1)$$G$$H$$k$$cw(H) \leq 2^k (3 + 1)$$\mathcal{G}_k$$4*2^k$$k$

Trataré de responder esta vieja pregunta suya, aunque no estoy seguro de que mi respuesta sea concluyente, pero debería apuntarlo en la dirección correcta.

Primero analicemos el ancho lineal de la camarilla. Si un gráfico tiene un ancho de camarilla lineal , y uno agrega vértice al gráfico, ese vértice siempre se puede colocar primero en el orden con un color único. Por lo tanto, el ancho lineal de la camarilla solo aumenta como máximo 1 cuando agrega un vértice.$k$$1$

Gurski y Wanke mostraron en "Sobre la relación entre el ancho NLC y el ancho lineal NLC" que los coógrafos tienen un ancho de camarilla lineal ilimitado.

Dado que los coógrafos tienen un ancho de camarilla lineal ilimitado pero un ancho de camarilla acotado, cualquier buena descomposición de camarilla debe tener una estructura de árbol. Debemos demostrar que podemos forzar arbitrariamente muchas ramas profundas. Ahora hacemos lo que hacemos para los árboles, construimos un árbol con 2 ^ k hojas, agregamos k vértices y cada hoja está conectada a un subconjunto único de vértices nuevos.