Apa yang diketahui tentang kekerasan indeks kromatik untuk kelas grafik terbatas?

9

Ada sebuah makalah yang bagus dari tahun 1991 yang berisi tiga diagram tentang keluarga grafclass berbeda yang menunjukkan apa yang diketahui tentang kekerasan menentukan indeks kromatik untuk mereka. Apakah ada berita sejak saat itu tentang ini?

Saya paling tertarik dengan apa yang diketahui tentang grafik dengan angka kromatik terbatas. Keingintahuan saya telah meningkat oleh /mathpro/238448/hypergraph-edge-colouring .

graph-theory np-hardness graph-colouring domotorp
sumber
graphclasses.org memiliki daftar berdasarkan kelas kerumitan pengujian apakah grafik 3-colourable dan lainnya untuk menguji apakah itu k-colourable . Ia juga memiliki daftar besar kelas yang nomor kromatiknya dibatasi .
Peter Taylor
@ Peter: Saya tidak bisa menemukan indeks berwarna di basis data.
domotorp

Jawaban:

2

Inilah satu hasil pencarian yang sangat relevan:

Koreas, Diamantis P. (1997), "NP-kelengkapan indeks kromatik dalam grafik bebas segitiga dengan titik maksimum derajat 3", Appl. Matematika Komputasi. 83 (1): 13–17 .

Judulnya cukup jelas.

David Eppstein
sumber
5
Jika judulnya cukup jelas, maka itu adalah hasil yang sangat sepele. Maksud saya makalah 1981 oleh Holyer yang menunjukkan kelengkapan NP dari indeks kromatik sebenarnya memberikan grafik kubik bebas segitiga. (Dalam grafik kubik, seseorang dapat dengan mudah mengganti setiap segitiga dengan sebuah simpul ketika mempelajari apakah indeks kromatiknya adalah 3 atau 4.)
domotorp