„Zupełnie różne zabarwienie hypergraph” - znany problem?

Interesuje mnie następujący problem: Biorąc pod uwagę zestaw X i podzbiory X_1, ..., X_n z X, znajdź kolorystykę elementów X za pomocą k kolorów, tak że wszystkie elementy w każdym X_i mają różne kolory. Mówiąc dokładniej, przyjmuję przypadek, w którym wszystkie X_i mają rozmiar k. Czy jest to znane w literaturze pod jakimś imieniem? Poszukuję charakterystyk kolorowych instancji i wyników dotyczących złożoności (P vs. NP-twardy). Na przykład dla k = 2 instancje koloryzujące odpowiadają grafom dwustronnym, a zatem problem można rozwiązać w czasie wielomianowym.

Uważam, że jest to znane w literaturze jako problem znalezienia silnego zabarwienia k dla hipergraphu w mundurze k. To powinno być dobre miejsce na rozpoczęcie: [PDF] .

Jest również co najwyżej tak mocno, jak -coloring wykres G = ( X , E ) , gdzie E jest utworzona przez co każdy X. I na klika. Twoje ograniczenie, że wszystkie X i mają rozmiar k, oznacza, że ​​możesz przykryć każdą krawędź G kliką na k wierzchołków.$k$$G=(X,E)$$E$$X_i$$X_i$$k$$G$$k$

Przynajmniej tak trudne jak -kolorowanie dowolnego wykresu G = ( V , E ) . Dla każdej krawędzi e = { u , v } masz podzbiór X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , … , x ( e , k ) } ; tutaj każdy x ( $k$$G = (V,E)$$e = \{u,v\}$$X_e = \{ u, v, x(e,3), x(e,4), \dotsc, x(e,k) \}$ jest fikcyjnym elementem, który nie jest obecny w żadnym innym podzbiorze. Jeśli można k -Kolor G , można łatwo znaleźć kolorystykę systemu zadanej (tylko pokolorować elementy fikcyjne łapczywie) i odwrotnie.$x(e,j)$$k$$G$

Zabarwienie, w którym każda hipersge jest polichromatyczna (lub tęcza ), jest również znana jako mocne zabarwienie .

Zauważ, że silne zabarwienie hipergrrafu jest właśnie właściwym zabarwieniem wykresu Gaifmana hipergrrafu. ( Wykres Gaifmana (lub wykres pierwotny lub 2-przekrojowy ) hipergrafu jest tworzony przez dodanie krawędzi między dowolnymi dwoma wierzchołkami, które pojawiają się razem w pewnym hipersgerze.)

Więc jeśli szukasz -colouring o r -uniform hipergraf H , a następnie można równoważnie szukać k -colouring wykresu Gaifman z H . Przypadek r = 2 odpowiada zabarwieniu wykresu, który jest czasem wielomianowym dla k = 2 i całkowitym NP dla k ≥ 3 . Oczywiście r < 2 jest trywialne, k < r nie prowadzi do żadnych rozwiązań, a wszystkie pozostałe przypadki są NP-kompletne.$k$$r$$H$$k$$H$$r=2$$k=2$$k\ge 3$$r <2$$k\lt r$

Przydatnym odniesieniem, które ma większość powyższych definicji, jest Witalij I. Wołoszin , Kolorowanie mieszanych hipergraphów: teoria, algorytmy i zastosowania , Fields Institute Monographs 17 , AMS, 2002, ISBN 0-8218-2812-6. Ta książka opisuje bardziej ogólny przypadek słabego zabarwienia, ze szczególnym naciskiem na połączenie dwóch rodzajów kolorowych krawędzi: krawędzi , które mają co najmniej dwa wierzchołki o wspólnym kolorze, oraz krawędzi D , które mają co najmniej dwa różne wierzchołki zabarwienie.$C$$D$