grafik di mana pewarnaan simpul dalam P tetapi set independen adalah NP lengkap

Apakah ada contoh kelas grafik yang masalah pewarnaan verteksnya ada di P tetapi himpunan independennya adalah masalah NP lengkap?

Pernyataan yang mungkin lebih umum (dengan bukti yang mudah) adalah bahwa masalah berikut sudah lengkap dengan NP:

Input: Grafik G, pewarnaan 3-G, integer k.

Pertanyaan: Apakah G memiliki ukuran k yang independen?

Ini dapat dibuktikan dengan pengurangan dari Perangkat Independen. Perhatikan bahwa jika kita mengambil grafik G, memilih beberapa tepi, dan membaginya dua kali (yaitu ganti tepi {u, v} dengan jalur u, x, y, v di mana x dan y memiliki derajat dua) maka angka kemandirian G meningkat tepat satu. (Anda dapat menambahkan tepat satu dari x atau y ke set mana pun yang independen di G, dan sebaliknya juga tidak sulit.) Jadi pertanyaannya jika grafik G dengan m edge memiliki set independen ukuran k, setara dengan pertanyaan apakah G ', yang merupakan hasil dari membagi semua tepi dalam G dua kali, memiliki seperangkat ukuran k + m yang independen. Tetapi perhatikan bahwa mudah untuk mendapatkan 3-pewarnaan G ', dengan mempartisi G' menjadi tiga set independen sebagai berikut: satu berisi simpul yang juga dalam G, dan dua kelas lainnya masing-masing berisi tepat satu dari dua " pengumpul " simpul untuk setiap tepi. Karenanya prosedur ini membangun grafik G 'dengan 3-pewarnaannya, sehingga menghitung angka kemandiriannya memberi Anda angka kemandirian dari grafik asli G.

Seharusnya referensi "masalah NP-lengkap pada grafik planar kubik 3-terhubung dan aplikasi mereka" oleh Uehara (makalah saya belum benar-benar melihat) membuktikan bahwa set independen adalah NP-lengkap bahkan untuk grafik planar bebas segitiga. Tetapi menurut teorema Grötzsch, mereka selalu 3-warna, dan pengujian untuk jumlah warna yang lebih kecil dari 3 mudah dalam grafik apa pun, sehingga mereka dapat secara optimal diwarnai dalam P.

Grafik lingkaran memiliki properti yang berlawanan: bagi mereka, mewarnai adalah NP lengkap tetapi masalah himpunan independen mudah.

Ini bukan jawaban baru melainkan klarifikasi referensi pertama dan mudah diperoleh untuk kekerasan SET INDEPENDEN dalam grafik planar kubik bebas segitiga: Catatan oleh Owen Murphy, Komputasi set independen dalam grafik dengan lingkar besar , Diskrit Terapan Matematika 35 (1992) 167-170 membuktikan itu

$n$$cn^k$$c>0$$k, 0\le k < 1$

$c$$c>0$

Pengurangan yang ditunjukkan oleh @ BartJansen adalah kasus khusus dalam bukti teorema Murphy.

Untuk properti yang berlawanan, grafik garis tampaknya lebih alami daripada grafik lingkaran sebagaimana dialamatkan oleh @DavidEppstein. Untuk grafik garis, COLORING adalah NP-complete tetapi SET INDEPENDEN mudah.