“Pewarnaan hypergraph semua-berbeda” - masalah yang diketahui?

Saya tertarik pada masalah berikut: Diberikan satu set X dan himpunan bagian X_1, ..., X_n dari X, temukan pewarnaan elemen-elemen X dengan k warna sehingga elemen-elemen di setiap X_i semuanya berwarna berbeda. Lebih khusus, saya melihat kasus di mana semua X_i berukuran k. Apakah ini dikenal dalam literatur dengan beberapa nama? Saya mencari penokohan contoh yang dapat diwarnai dan hasil pada kompleksitas (P vs NP-hard). Misalnya, untuk k = 2, instance berwarna sesuai dengan grafik bipartit, dan dengan demikian masalah dapat diselesaikan dalam waktu polinomial.

Saya percaya ini dikenal dalam literatur sebagai masalah menemukan pewarnaan k yang kuat untuk hypergraph k-uniform. Ini harus menjadi tempat yang baik untuk memulai: [PDF] .

Ini juga paling keras seperti -warna grafik G = ( X , E ) , di mana E dibentuk dengan membuat setiap X i menjadi sebuah klik. Batasan Anda bahwa semua X i berukuran k berarti Anda dapat menutup setiap sisi$k$$G=(X,E)$$E$$X_i$$X_i$$k$ dengan klik pada k simpul.$G$$k$

Setidaknya sekeras -warna grafik sewenang-wenang G = ( V , E ) . Untuk setiap tepi e = { u , v } Anda memiliki subset X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , … , x ( e , k ) $k$$G = (V,E)$$e = \{u,v\}$$X_e = \{ u, v, x(e,3), x(e,4), \dotsc, x(e,k) \}$ ; di sini masing-masing , Anda dapat dengan mudah menemukan pewarnaan dari sistem yang ditetapkan (cukup warna elemen dummy dengan rakus), dan sebaliknya.$x(e,j)$adalah elemen dummy yang tidak ada di subset lainnya. Jika Anda bisa -warna $k$$G$

Pewarnaan di mana setiap hyperedge adalah polikromatik (atau pelangi ) juga dikenal sebagai pewarnaan yang kuat .

Perhatikan bahwa pewarnaan yang kuat dari hypergraph adalah pewarnaan yang tepat dari grafik Gaifman dari hypergraph. ( Grafik Gaifman (atau grafik primal atau 2-bagian ) dari hypergraph dibentuk dengan menambahkan tepi antara dua simpul yang muncul bersama dalam beberapa hyperedge.)

$k$$r$$H$$k$$H$$r=2$$k=2$$k\ge 3$$r <2$$k\lt r$ mengarah ke tidak ada solusi, dan kasus-kasus lainnya semuanya NP-lengkap.

Referensi yang berguna yang memiliki sebagian besar definisi di atas adalah Vitaly I. Voloshin, Pewarnaan Campuran Hypergraphs: Teori, Algoritma dan Aplikasi , Fields Institute Monographs 17 , AMS, 2002, ISBN 0-8218-2812-6. Buku ini membahas kasus pewarnaan lemah yang lebih umum, dengan fokus khusus pada penggabungan dua jenis tepi berwarna: edges, yang memiliki setidaknya dua simpul dengan warna yang sama, dan D- edges, yang memiliki setidaknya dua simpul yang berbeda. warna.$C$$D$