Anak-anak terlarang untuk grafik treewidth terbatas

Pertanyaan ini mirip dengan salah satu pertanyaan saya sebelumnya. Hal ini diketahui bahwa adalah minor dilarang untuk grafik dari treewidth paling t .$K_{t+2}$$t$

Adakah keluarga yang dibangun dengan baik, parameter, dan tak terbatas grafik (selain grafik lengkap dan grafik kisi) yang minimal anak di bawah umur terlarang untuk grafik setiap treewidth. Dengan kata lain, apakah ada grafik eksplisit pada r simpul (yang bukan merupakan grafik lengkap) sehingga G r adalah minor terlarang untuk grafik treewidth paling banyak r , di mana r adalah fungsi dari t ?$G_r$$r$$G_r$$r$$r$$t$

Set lengkap anak terlarang di bawah umur dikenal untuk grafik treewidth paling banyak tiga. Lihat artikel Wikipedia ini untuk lebih jelasnya.

Apakah set lengkap terlarang anak di bawah umur dari grafik treewidth paling banyak diketahui?

Jika G dibentuk dari grafik yang lebih kecil H yang bukan merupakan klik dengan menambahkan dua simpul x dan y, sedemikian sehingga x dan y tidak berdekatan satu sama lain tetapi berdekatan dengan semua simpul G lainnya, maka . Sebab, dalam setiap dekomposisi pohon G , baik x dan$tw(G)=tw(H)+2$$G$$x$ memiliki subtree yang terpisahkan atau mereka memiliki subtree yang tumpang tindih. Jika mereka memiliki sub pohon yang terpisah, semua sub pohon yang lain harus menyertakan jalur terpendek antara pohon untuk x dan y , dari mana diikuti bahwa treewidth adalah n - $y$$x$$y$$n-2$; asumsi bahwa bukan klik kemudian dapat digunakan untuk menunjukkan bahwa n - 2 ≥ t w ( H ) + 2 . Atau jika x dan y memiliki subtree yang tumpang tindih, setiap simpul lainnya harus memiliki subtree yang menyentuh persimpangan dari dua subtree x dan y , dan kita dapat membatasi dekomposisi pohon ke persimpangan itu, memberikan dekomposisi pohon di mana x dan y berpartisipasi dalam setiap simpul pohon.$H$$n-2\ge tw(H)+2$$x$$y$$x$$y$$x$$y$

Ini menyiratkan bahwa grafik hyperoctahedral dengan simpul 2 k adalah minor terlarang minimal untuk lebar 2 k - 3 . Sebab, oktahedral grafik $K_{2,2,2,\dots}$$2k$$2k-3$ adalah minor terlarang minimal untuk lebar tiga, dari mana argumen di atas menunjukkan bahwa grafik hyperoctahedral memiliki lebar2k-$K_{2,2,2}$$2k-2$. Dan jika ada kontraksi tepi atau penghapusan tepi yang dilakukan dalam grafik hyperoctahedral, simetri grafik memungkinkan kita untuk mengasumsikan bahwa operasi terjadi pada salah satu dari dua belas tepi di octahedron dasar, menyebabkan lebar dan lebar semua hyperoctahedra dibangun dari itu untuk berkurang.

(Kelas grafik lain yang harus Anda sertakan dalam pertanyaan Anda bersama dengan grafik lengkapnya adalah grafik kisi. An jaringan memiliki treewidth r . Ini terpisah dari anak di bawah umur graf lengkap karena planar dan karena itu tidak memiliki minor lengkap dengan lebih dari empat simpul. Ini bukan minor terlarang minimal, karena beberapa perubahan kecil (seperti mengontrak sudut sudut) tidak mengubah treewidth-nya.)$r\times r$$r$

$\leq 4$