Cliquewidth of Almost Cographs

(Saya memposting pertanyaan ini ke MathOverflow dua minggu lalu, tetapi sejauh ini tanpa jawaban yang ketat)

Saya memiliki pertanyaan tentang ukuran lebar grafik dari grafik sederhana yang tidak diarahkan. Sudah diketahui bahwa cographs (grafik yang dapat dibangun dengan operasi disjoint union dan komplementasi, mulai dari simpul terisolasi) memiliki klik paling banyak 2. (Courcelle et al, Batas atas ke lebar klik grafik). Sekarang mempertimbangkan beberapa tetap non-negatif bilangan bulat k, dan mempertimbangkan kelas grafik grafik sehingga untuk setiap G = ( V , E ) ∈ G k ada satu set S paling banyak simpul k sehingga G [ V - S ] adalah gambar. Karena kelas grafik $\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$ juga dapat dilihat sebagai kelas grafik yang dapat dibangun dari cographs dengan menambahkan paling k simpul, kelas ini juga telah disebut cographs + k v .$\mathcal{G} _k$$k$$kv$

Pertanyaan saya adalah: apa yang ketat terikat pada cliquewidth grafik di , yaitu grafik yang dapat berubah menjadi cograph dengan menghapus simpul k?$\mathcal{G}_k$

Diketahui bahwa jika grafik diperoleh dari H dengan menghapus simpul k maka c w ( H ) ≤ 2 k ( c w ( G ) + 1 ) . Ini menunjukkan bahwa jika suatu cograf G dapat diperoleh dari grafik H dengan menghapus k k , maka c w ( H ) ≤ 2 k ( 3 + 1 ) , dan karenanya klik setiap grafik dalam G$G$$H$$k$$cw(H) \leq 2^k (cw(G) + 1)$$G$$H$$k$$cw(H) \leq 2^k (3 + 1)$$\mathcal{G}_k$paling banyak . Saya tidak yakin apakah ketergantungan eksponensial pada k ini diperlukan. Dalam konteks ini saya juga akan tertarik pada penurunan maksimum dalam cliquewidth dengan menghapus suatu titik; yaitu jika kita menghapus satu titik dari grafik, berapa banyak yang bisa dikecilkan?$4*2^k$$k$

Saya akan mencoba menjawab pertanyaan lama Anda ini, meskipun saya tidak yakin jawaban saya konklusif tetapi harus mengarahkan Anda ke arah yang benar.

$k$$1$

Gurski dan Wanke menunjukkan dalam "Pada hubungan antara NLC-width dan linear NLC-width" bahwa cographs memiliki klik-linear linear yang tidak terikat.

Karena cographs memiliki lebar klik-linear yang tidak terikat tetapi lebar-klik-terikat, setiap dekomposisi klik yang bagus harus memiliki struktur pohon. Kita harus menunjukkan bahwa kita dapat memaksa banyak cabang yang dalam secara sewenang-wenang. Sekarang kita lakukan seperti yang kita lakukan untuk pohon, membangun pohon dengan pada 2 ^ k daun menambahkan simpul k dan setiap daun terhubung ke subset unik dari simpul baru.