Grafik di mana setiap pemisah minimal adalah set independen

Latar Belakang: Misalkan menjadi dua simpul dari graf tak berarah . Himpunan simpul adalah -pemisah jika dan milik komponen terhubung yang berbeda dari . Jika tidak ada himpunan bagian yang tepat dari a -separator adalah -separator maka adalah minimum u, v -separator. Set vertex S \ subseteq V adalah pemisah (minimal) jika ada simpul u, v sedemikian sehingga S adalah (minimal) u, v -pemisah.$u, v$$G=(V,E)$$S\subseteq V$$u,v$$u$$v$$G-S$$u,v$$S$$u,v$$S$$u,v$$S\subseteq V$$u, v$$S$$u,v$

Teorema G. Dirac yang terkenal menyatakan bahwa suatu graf tidak memiliki siklus panjang paling tidak empat (disebut triangulated atau chordal graph) jika dan hanya jika setiap pemisah minimalnya adalah klik. Juga diketahui bahwa grafik triangulasi dapat dikenali dalam waktu polinomial.

Pertanyaan saya: Apa grafik di mana setiap pemisah minimal adalah set independen? Apakah grafik ini dipelajari? Dan apa kompleksitas pengakuan dari grafik ini? Contoh untuk grafik tersebut termasuk pohon dan siklus.

Grafik Anda telah ditandai oleh makalah ini http://arxiv.org/pdf/1103.2913.pdf .

Sunting: Dalam makalah di atas terbukti bahwa grafik di mana setiap pemisah minimal adalah set independen adalah persis yang tidak mengandung siklus dengan tepat satu akor.

Grafik yang tidak mengandung siklus dengan tepat satu akor telah dipelajari secara mendalam oleh Trotignon dan Vuskovic, Teorema Struktur untuk Grafik tanpa Siklus dengan Akor Unik dan Konsekuensinya , J. Graph Theory 63 (2010) 31-67 DOI . Sebagai hasil dari makalah ini, grafik ini dapat dikenali dalam waktu polinomial. (Namun, makalah ini tidak menunjukkan koneksi ke pemisah minimal independen!)

Sunting (17 September 2013): Baru-baru ini (lihat di sini ), Terry Mckee menjelaskan semua grafik di mana setiap pemisah simpul minimum adalah klik atau satu set independen. Ternyata ini adalah '' jumlah ujung '' dari grafik chordal dan grafik di mana setiap pemisah simpul minimum adalah satu set independen.

Tampaknya karakterisasi awal dari grafik di mana setiap pemisah minimal adalah set independen muncul di TA McKee, "Grafik pemisah independen," Utilitas Mathematica 73 (2007) 217--224. Ini adalah grafik di mana tidak ada siklus memiliki akor yang unik (atau, yang setara, di mana, dalam setiap siklus, setiap akor memiliki akord penyilangan).

Ada dua makalah baru pada grafik tanpa siklus memiliki tepat satu akor. Keduanya terutama berhubungan dengan pewarnaan grafik ini: http://arxiv.org/abs/1309.2749 dan http://arxiv.org/abs/1311.1928 .

Kemudian juga memberikan algoritma pengenalan . Tetapi yang lebih cepat dalam waktu sudah disediakan di koran oleh Trotignon dan Vuskovic (dikutip dalam jawaban oleh user13136).$O(m^2n)$$O(mn)$