A largura da camarilha é preservada sob contrações da borda?

13

Seja uma classe de gráficos com largura de clique limitada. Em cada gráfico em G, algumas arestas são contraídas (por exemplo, aleatoriamente). Agora a largura da camarilha ainda é limitada?GG

Caso (em geral) não seja mais limitado, eu estaria muito interessado em um contra-exemplo.

graph-theory co.combinatorics cliquewidth Martin Lackner
fonte

Respostas:

16

Isso pode ser uma pré-resposta: neste artigo do arXiv de 2007 (Problema 4.9), é declarado como um problema em aberto se é possível encontrar um gráfico e uma aresta { x , y } ∈ E ( G ) tal que c w ( G ) < c w ( G x , y ) , onde G x , y é o gráfico G com a aresta { x , y } contraída.G{x,y}∈E(G)cW(G)<cW(Gx,y)Gx,yG{x,y}

Mathieu Chapelle
fonte
Muito obrigado pela sua resposta! Essa é uma referência valiosa para mim. No caso ninguém tenha resolvido, entretanto, a minha pergunta é mais ou menos respondeu :)
Martin Lackner
Esse problema não é o contrário do que está sendo perguntado aqui?
Tsuyoshi Ito
Somente no sentido em que essa pergunta pede um contra-exemplo.
Martin Lackner
17

Este artigo recente finalmente prova que as contrações das arestas não preservam a propriedade que um conjunto de gráficos delimitou a largura da clique.

user13136
fonte