Cliquewidth of Almost Cographs

( Wysłałem to pytanie do MathOverflow dwa tygodnie temu, ale jak dotąd bez ścisłej odpowiedzi)

Mam pytanie dotyczące miar szerokości wykresu niekierowanych prostych wykresów. Powszechnie wiadomo, że wykresy (wykresy, które można budować za pomocą operacji rozłącznego łączenia i uzupełniania, poczynając od izolowanych wierzchołków) mają najwyżej 2-krotność (Courcelle i in., Górne granice szerokości kliki wykresów). Teraz rozważmy pewną stałą nieujemną liczbę całkowitą k i rozważmy klasę grafów grafów, tak że dla każdego G = ( V , E ) ∈ G k jest zestaw S co najwyżej k wierzchołków, taki że G [ V - S ] to cograph. Ponieważ klasa grafów $\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$$\mathcal{G} _k$ można również postrzegać jako klasę wykresów, które można zbudować z cografów, dodając co najwyżej wierzchołków, ta klasa została również nazwana cographs + k v .$k$$kv$

Moje pytanie brzmi: co jest ściśle związane z płynnością na wykresach w , tj. Wykresy, które można przekształcić w cograph poprzez usunięcie k wierzchołków?$\mathcal{G}_k$

Wiadomo, że jeśli wykres uzyskuje się z H , usuwając k wierzchołków, a następnie c wagowo ( H ) ≤ 2 k ( c w ( G ) + 1 ) . Oznacza to, że jeśli kograf G można uzyskać z krzywej H usuwając k wierzchołków, a następnie C w ( H ) ≤ 2 K ( 3 + 1 jest co najwyżej 4 * 2 $G$$H$$k$$cw(H) \leq 2^k (cw(G) + 1)$$G$$H$$k$ , a zatem cliquewidth wykresu w G$cw(H) \leq 2^k (3 + 1)$$\mathcal{G}_k$$4*2^k$ . Nie jestem pewien, czy ta wykładnicza zależność od jest konieczna. W tym kontekście byłbym również zainteresowany maksymalnym zmniejszeniem szerokości kliki poprzez usunięcie wierzchołka; tzn. jeśli usuniemy pojedynczy wierzchołek z wykresu, o ile można zmniejszyć szerokość kliki?$k$

Postaram się odpowiedzieć na to twoje stare pytanie, chociaż nie jestem pewien, czy moja odpowiedź jest rozstrzygająca, ale powinna wskazać właściwy kierunek.

Najpierw omówmy liniową szerokość kliki. Jeśli wykres ma liniową szerokość kliki , a jeden dodaje do wykresu 1 wierzchołek, ten wierzchołek zawsze może być umieszczony w kolejności z unikalnym kolorem. Dlatego liniowa szerokość kliki zwiększa się tylko o maksymalnie 1 po dodaniu wierzchołka.$k$$1$

Gurski i Wanke pokazali w „O związku między szerokością NLC a liniową szerokością NLC”, że kartografy mają nieograniczoną liniową szerokość kliki.

Ponieważ kartografy mają nieograniczoną liniową szerokość kliki, ale ograniczoną szerokość kliki, każdy dobry rozkład kliki musi mieć strukturę drzewa. Musimy pokazać, że możemy zmusić dowolnie wiele głębokich gałęzi. Teraz robimy to samo, co w przypadku drzew, konstruujemy drzewo z 2 ^ k liści dodających k wierzchołków, a każdy liść jest połączony z unikalnym podzbiorem nowych wierzchołków.