Set independen maksimal dan maksimal

Apakah ada sesuatu yang diketahui tentang kelas grafik dengan properti yang semua set independen maksimal memiliki kardinalitas yang sama dan karenanya IS maksimum?

Sebagai contoh, ambil satu set poin di pesawat dan pertimbangkan grafik persimpangan di antara semua segmen antara pasangan poin di set. (segmen-> simpul, persimpangan-> tepi). Grafik ini akan memiliki properti di atas, karena semua IS maksimal sesuai dengan triangulasi dari set titik asli. Apakah ada kategori grafik lain yang diketahui memiliki properti ini? Bisakah properti ini mudah diuji?

Grafik semacam itu disebut grafik tertutup . Berikut adalah makalah terbaru tentang subjek yang mencantumkan beberapa referensi yang berguna. Seperti yang disebutkan oleh Suresh, masalah pengakuannya adalah co-NP-complete.

Perhatikan bahwa set independen grafik membentuk kompleks kesederhanaan abstrak. Kompleks sederhana yang muncul dengan cara ini disebut "kompleks kemerdekaan" atau "kompleks bendera". Kompleks simplisial dikatakan murni jika setiap simpleks maksimal memiliki kardinalitas yang sama. Jadi, Anda dapat menemukan beberapa makalah yang relevan dengan mencari "kompleks kemerdekaan murni" atau "kompleks bendera murni."

Properti MAXIMAL = MAXIMUM untuk set independen dalam grafik dan struktur kombinatorial yang lebih umum adalah penting. Akan menarik untuk memahami grafik di mana properti ini berlaku untuk semua subgraph yang diinduksi. Satu kasus abstrak umum di mana kita memiliki MAXIMUM = MAXIMAL adalah ketika ada struktur matroid yang mendasarinya, tetapi ada banyak kasus lain, seperti kasus grafik planar maksimal yang disebutkan dalam pertanyaan. Berikut ini adalah contoh terkait: Pertimbangkan n titik pada bidang dalam posisi cembung dan biarkan k menjadi bilangan bulat. Pertimbangkan grafik yang simpulnya adalah segmen garis antara titik-titik ini di mana dua simpul berdekatan jika segmen garis tidak bersilangan. Dress membuktikan bahwa untuk grafik ini MAXIMIM = MAXIMAL untuk set independen.