Keluarga grafik yang memiliki algoritma waktu polinomial untuk menghitung bilangan kromatik

Posting diperbarui pada tanggal 31 Agustus : Saya menambahkan ringkasan jawaban saat ini di bawah pertanyaan awal. Terima kasih atas semua jawaban yang menarik! Tentu saja, semua orang dapat terus memposting temuan baru.

Untuk kelompok grafik mana terdapat algoritma waktu polinomial untuk menghitung bilangan kromatik ?$\chi(G)$

Masalahnya dipecahkan dalam waktu polinomial ketika (grafik bipartit). Secara umum ketika , menghitung bilangan kromatik adalah NP-hard, tetapi ada banyak keluarga grafik di mana ini tidak terjadi. Misalnya, siklus pewarnaan dan grafik sempurna dapat dilakukan dalam waktu polinomial.$\chi(G) = 2$$\chi(G) \ge 3$

Juga, untuk banyak kelas grafik, kita dapat mengevaluasi polinomial kromatik yang sesuai; beberapa contoh di Mathworld .

Saya kira sebagian besar di atas adalah pengetahuan umum. Saya dengan senang hati akan mengetahui apakah ada keluarga grafik lain (non-sepele) yang pewarnaan graf minimumnya dapat dipecahkan dalam waktu polinomial.

Secara khusus, saya tertarik pada algoritma yang tepat dan deterministik tetapi merasa bebas untuk menunjukkan algoritma acak atau algoritma aproksimasi yang menarik.

Pembaruan (31 Agustus):

Terima kasih kepada semua orang karena mengirimkan jawaban yang menarik. Berikut ringkasan jawaban dan rujukan.

Grafik sempurna dan hampir sempurna

• Algoritma Geometris dan Optimalisasi Kombinatorial (1988), Bab 9 (Set stabil dalam grafik). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.

  Bab 9 buku ini menunjukkan bagaimana menyelesaikan masalah pewarnaan melalui masalah penutup klik tertimbang minimum. Karena mereka bergantung pada metode ellipsoid, algoritma ini mungkin tidak terlalu berguna dalam praktiknya. Juga, bab ini memiliki daftar referensi yang bagus untuk berbagai kelas grafik sempurna.

• Optimalisasi Kombinatorial (2003), Volume B, Bagian VI Alexander Schrijver.

  Buku ini memiliki tiga bab yang ditujukan untuk grafik sempurna dan kemudahan waktu polinomial mereka. Saya hanya melihat sekilas, tetapi pendekatan dasarnya tampak sama seperti di buku sebelumnya.

• Karakterisasi grafik b-perfect (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Grafik dengan lebar pohon terbatas atau lebar klik

• Kumpulan dominasi tepi dan pewarnaan pada grafik dengan lebar klik-tetap (2001). Daniel Kobler, Udi Rotics

  Algoritme di sini memerlukan ekspresi-k (rumus aljabar untuk membuat grafik dengan lebar klik-terikat) sebagai parameter. Untuk beberapa grafik, ungkapan ini dapat dihitung dalam waktu linier.

• Yaroslav menunjukkan metode penghitungan warna dalam grafik lebar pohon yang dibatasi. Lihat jawabannya di bawah.

Dua kelompok grafik studi ini di mana simpul atau tepi dapat ditambahkan atau dihapus.$k$

• Kompleksitas parameterisasi pewarnaan vertex (2003). Leizhen Cai.

  Pewarnaan dapat diselesaikan dalam waktu polinomial saat menambah atau menghapus tepi (untuk tetap ) dalam grafik split .$k$$k$

• Masalah pewarnaan parameter pada grafik chordal (2006). Dániel Marx.

  Untuk tetap , grafik chordal yang edge ditambahkan, dapat diwarnai dalam waktu polinomial.$k$$k$

Grafik tidak mengandung subgraf tertentu

• Menentukan k-Colorability dari Grafik P5-Free dalam Waktu Polinomial (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.

• 3-mewarnai grafik AT-free dalam waktu polinomial (2010). Juraj Stacho.

Mewarnai quadtrees

• Algoritma untuk pewarnaan quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.

Seperti yang Anda amati, semua grafik yang sempurna dapat diwarnai dalam waktu polinomial, tetapi saya pikir buktinya melibatkan algoritma ellipsoid untuk pemrograman linier (lihat buku karya Grötschel, Lovász, dan Schrijver) daripada apa pun yang langsung dan kombinatorial. Ada banyak kelas grafik yang berbeda yang merupakan subkelas dari grafik sempurna dan memiliki algoritma pewarnaan yang lebih mudah; grafik chordal, misalnya, dapat diwarnai dengan rakus menggunakan urutan eliminasi sempurna.

Semua grafik yang terhubung secara lokal (grafik di mana setiap titik memiliki lingkungan yang terhubung) dapat berwarna 3 dalam waktu polinomial, ketika pewarnaan ada: hanya memperpanjang segitiga pewarnaan dengan segitiga.

Grafik tingkat tiga maksimum dapat diwarnai dalam waktu polinomial: mudah untuk menguji apakah mereka bipartit, dan jika tidak maka mereka hanya membutuhkan tiga warna atau mereka memiliki K4 sebagai komponen yang terhubung dan memerlukan empat warna (teorema Brooks).

Grafik planar bebas segitiga dapat diwarnai dalam waktu polinomial, untuk alasan yang sama: grafik planar paling banyak 3-kromatik (teorema Grötzsch).

grafik b-perfect memungkinkan induksi 5-siklus (tidak seperti grafik sempurna), dan ditunjukkan memiliki algoritma waktu polinomial untuk pewarnaan oleh Hoàng, Maffray, dan Mechebbek, Karakterisasi grafik b-perfect , arXiv: 1004.5306 , 2010.

(Sangat disayangkan bahwa ringkasan indah dari kelas grafik di ISGCI hanya mencakup cliquewidth, set independen, dan dominasi. Ini tidak termasuk informasi tentang pewarnaan.)

Juga untuk grafik lebar klik terikat (yang lebih umum daripada treewidth): Kobler dan Rotics .

$n^{f(k)}$

Juga, lebar klik sulit untuk dihitung, tetapi ada algoritme aproksimasi oleh Oum dan Seymour, "memproksimasi lebar klik dan lebar cabang" (dengan perkiraan eksponensial).

$k$

Setiap kelompok grafik dengan lebar sebatas pohon akan memiliki algoritma waktu polinomial untuk menghitung bilangan kromatik. Gamarnik mengurangi masalah penghitungan warna dengan margin komputasi dari Bidang Acak Markov tertentu yang didefinisikan pada grafik yang sama. Hasil berikut karena marjinal MRF pada grafik lebar pohon terikat dapat dihitung dalam waktu polinomial dengan algoritma pohon persimpangan .

Pembaruan 8/26 : Berikut adalah contoh "# pewarnaan" <-> pengurangan margin. Ini membutuhkan dimulai dengan pewarnaan yang tepat, yang dapat ditemukan dalam waktu polinomial untuk grafik lebar pohon terbatas dengan versi max-plus dari algoritma pohon persimpangan. Sekarang untuk dipikirkan ... Anda tidak perlu # pewarnaan untuk nomor berwarna, hanya satu pewarnaan yang tepat

$P_5$$C_5$$P_5$

$2P_3$

Ada juga hasil oleh Daniel Marx mengenai kompleksitas masalah bilangan kromatik pada grafik yang dapat dibuat chordal oleh paling banyak penghapusan k verteks; untuk setiap k diperbaiki masalah ini bersifat polinomial ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Algoritma untuk mewarnai quadtrees .
M. Bern, D. Eppstein, dan B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87-94, 2002.

Kami mempertimbangkan beberapa variasi masalah pewarnaan kuadrat sehingga tidak ada dua kotak yang berdekatan yang berwarna sama. Kami memberikan algoritme waktu linear sederhana untuk quadtrees 3-warna seimbang dengan adjacency edge, 4 quadtrees tidak-seimbang dengan adjacency tepi, dan 6-warna quadtrees seimbang atau tidak seimbang dengan adjacency sudut. Jumlah warna yang digunakan oleh dua algoritma pertama adalah optimal; untuk algoritma ketiga, 5 warna kadang-kadang mungkin diperlukan.