Cliquewidth of Quase Cographs

( Publiquei esta pergunta no MathOverflow há duas semanas, mas até agora sem uma resposta rigorosa)

Tenho uma pergunta sobre medidas de largura de gráfico de gráficos simples não direcionados. É sabido que as cografias (gráficos que podem ser construídos pelas operações de união e complementação disjuntas, a partir de vértices isolados) têm uma largura de cliques no máximo 2. (Courcelle et al., Limites superiores à largura de clique dos gráficos). Agora considere algum número inteiro não negativo fixo k e considere a classe de gráficos de gráficos, de modo que, para todo exista um conjunto de em a maioria dos k vértices é tal que é uma cografia. Como a classe de gráficos também pode ser vista como a classe de gráficos que podem ser criados a partir de cografias adicionando no máximo$\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$$\mathcal{G} _k$$k$vértices, essa classe também foi chamada de cographs + .$kv$

Minha pergunta é: qual é o limite limitado da largura de cliques dos gráficos em , ou seja, os gráficos que podem ser transformados em uma cografia excluindo k vértices?$\mathcal{G}_k$

Sabe-se que se um gráfico é obtido de excluindo vértices, então . Isso mostra que se uma cograph pode ser obtida de um gráfico excluindo vértices, então e, portanto, a largura de cliques de um gráfico em é no máximo . Não tenho certeza se essa dependência exponencial de é necessária. Nesse contexto, eu também estaria interessado na diminuição máxima da largura de cliques, excluindo um vértice; ou seja, se excluirmos um único vértice de um gráfico, quanto pode diminuir a largura de cliques?$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$

Tentarei responder a essa sua antiga pergunta, embora não tenha certeza de que minha resposta seja conclusiva, mas ela deve indicar a direção certa.

Primeiro vamos discutir largura de clique linear. Se um gráfico tiver largura de clique linear e adicionar vértice ao gráfico, esse vértice sempre poderá ser colocado primeiro na ordem com uma cor exclusiva. Portanto, a largura de clique linear só aumenta no máximo 1 quando você adiciona um vértice.$k$$1$

Gurski e Wanke mostraram em "Sobre a relação entre largura de NLC e largura de NLC linear" que as cografias têm largura de clique linear ilimitada.

Como as cografias têm largura de clique linear ilimitada, mas largura de clique limitada, qualquer boa decomposição de clique deve ter uma estrutura em árvore. Devemos mostrar que podemos forçar arbitrariamente muitos ramos profundos. Agora fazemos o que fazemos para as árvores, construímos uma árvore com 2 ^ k folhas e adicionamos k vértices e cada folha é conectada a um subconjunto exclusivo de novos vértices.