"All-different hypergraph coloring" - bekanntes Problem?

Ich interessiere mich für das folgende Problem: Wenn eine Menge X und Teilmengen X_1, ..., X_n von X gegeben sind, finde eine Färbung der Elemente von X mit k Farben, so dass die Elemente in jedem X_i alle unterschiedlich gefärbt sind. Insbesondere betrachte ich den Fall, in dem alle X_i die Größe k haben. Ist dies in der Literatur unter einem Namen bekannt? Ich suche nach Charakterisierungen von färbbaren Instanzen und Ergebnissen zur Komplexität (P vs. NP-hart). Zum Beispiel entsprechen färbbare Instanzen für k = 2 zweigeteilten Graphen, und somit kann das Problem in Polynomzeit gelöst werden.

Ich glaube, dies ist in der Literatur als das Problem bekannt, eine starke k-Färbung für einen k-einheitlichen Hypergraphen zu finden. Dies sollte ein guter Anfang sein: [PDF] .

Es ist auch höchstens so schwer wie die Färbung eines Graphen , wobei gebildet wird, indem jedes zu einer Clique gemacht wird. Ihre Einschränkung, dass alle die Größe bedeutet, dass Sie jede Kante von mit einer Clique auf Ecken abdecken können .$k$$G=(X,E)$$E$$X_i$$X_i$$k$$G$$k$

Mindestens so hart wie die Färbung eines beliebigen Graphen . Für jede Kante Sie eine Teilmenge ; hier ist jedes ein Dummy-Element, das in keiner anderen Teilmenge vorhanden ist. Wenn Sie Farbe , können Sie leicht eine Färbung des eingestellten Systems finden (färben Sie einfach die Dummy-Elemente gierig ein) und umgekehrt.G = ( V , E ) e = { u , v } X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , ... , x ( e , k ) } x ( e , j ) k $k$$G = (V,E)$$e = \{u,v\}$$X_e = \{ u, v, x(e,3), x(e,4), \dotsc, x(e,k) \}$$x(e,j)$$k$$G$

Eine Färbung, bei der jeder Hyperedge polychrom (oder Regenbogen ) ist, wird auch als kräftige Färbung bezeichnet .

Beachten Sie, dass eine starke Färbung eines Hypergraphen genau eine richtige Färbung des Gaifman-Graphen des Hypergraphen ist. (Der Gaifman-Graph (oder der Ur-Graph oder der 2-Abschnitt ) eines Hypergraphen wird durch Hinzufügen von Kanten zwischen zwei beliebigen Scheitelpunkten gebildet, die in einem Hyperedge zusammen auftreten.)

Wenn Sie also nach einer Farbe eines r- einheitlichen Hypergraphen H suchen, können Sie gleichermaßen nach einer k- Farbe des Gaifman-Graphen von H suchen . Der Fall r = 2 entspricht der Graphenfärbung, die für k = 2 polynomial und für k ≥ 3 NP-vollständig ist . Offensichtlich ist r < 2 trivial, k < r führt zu keinen Lösungen, und die anderen Fälle sind alle NP-vollständig.$k$$r$$H$$k$$H$$r=2$$k=2$$k\ge 3$$r <2$$k\lt r$

Eine nützliche Referenz, die die meisten der obigen Definitionen aufweist, ist Vitaly I. Voloshin, Coloring Mixed Hypergraphs: Theorie, Algorithmen und Anwendungen , Fields Institute Monographs 17 , AMS, 2002, ISBN 0-8218-2812-6. Dieses Buch behandelt den allgemeineren Fall von schwachen Färbungen, wobei der Schwerpunkt auf der Kombination zweier Arten von farbigen Kanten liegt: Kanten, die mindestens zwei Scheitelpunkte mit einer gemeinsamen Farbe aufweisen, und D- Kanten, die mindestens zwei Scheitelpunkte mit unterschiedlichen Farben aufweisen Farben.$C$$D$