“Coloração hipergráfica diferente” - problema conhecido?

Estou interessado no seguinte problema: Dado um conjunto X e subconjuntos X_1, ..., X_n de X, encontre uma coloração dos elementos de X com k cores, de modo que os elementos em cada X_i sejam todos de cores diferentes. Mais especificamente, estou analisando o caso em que todos os X_i são do tamanho k. Isso é conhecido na literatura sob algum nome? Estou procurando caracterizações de instâncias coloridas e resultados de complexidade (P vs. NP-rígido). Por exemplo, para k = 2, instâncias coloridas correspondem a gráficos bipartidos e, portanto, o problema pode ser resolvido em tempo polinomial.

Acredito que isso seja conhecido na literatura como o problema de encontrar uma forte coloração k para um hipergrafo k-uniforme. Este deve ser um bom lugar para começar: [PDF] .

Também é, no máximo tão duro como -coloring um gráfico G = ( X , E ) , onde E é formada fazendo com que cada X i em uma clique. Sua restrição que tudo X i são de tamanho k significa que você pode cobrir cada aresta de G com um clique em k vértices.$k$$G=(X,E)$$E$$X_i$$X_i$$k$$G$$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$

Uma coloração em que toda hipérbole é policromática (ou arco - íris ) também é conhecida como coloração forte .

Observe que uma coloração forte de um hipergrafo é precisamente uma coloração adequada do gráfico Gaifman do hipergrafo. (O gráfico de Gaifman (ou gráfico primordial ou 2 seções ) de um hipergrafo é formado pela adição de arestas entre quaisquer dois vértices que aparecem juntos em alguma hiper-borda.)

$k$$r$$H$$k$$H$$r=2$$k=2$$k\ge 3$$r <2$$k\lt r$

$C$$D$