Estoy interesado en el siguiente problema: dado un conjunto X y los subconjuntos X_1, ..., X_n de X, encuentre una coloración de los elementos de X con k colores de manera que los elementos en cada X_i sean todos de colores diferentes. Más específicamente, estoy mirando el caso donde todos los X_i son de tamaño k. ¿Es esto conocido en la literatura con algún nombre? Estoy buscando caracterizaciones de instancias coloreables y resultados de complejidad (P vs. NP-hard). Por ejemplo, para k = 2, las instancias colorables corresponden a gráficos bipartitos y, por lo tanto, el problema puede resolverse en tiempo polinómico.
cc.complexity-theory
reference-request
np-hardness
hypergraphs
Falk Hüffner
fuente
fuente
Respuestas:
Creo que esto se conoce en la literatura como el problema de encontrar una coloración k fuerte para una hipergrafía k-uniforme. Este debería ser un buen lugar para comenzar: [PDF] .
fuente
También es, como máximo, tan difícil como colorear una gráfica , donde se forma al convertir cada en una camarilla. Su restricción de que todas las son de tamaño significa que puede cubrir cada borde de con una camarilla en vértices.G = ( X , E ) E X i X i k G kk G = ( X, E) mi Xyo Xyo k sol k
fuente
fuente
Un colorante en el que cada hiperedge es policromático (o arcoíris ) también se conoce como un colorante fuerte .
Tenga en cuenta que una fuerte coloración de una hipergrafía es precisamente una coloración adecuada del gráfico de Gaifman de la hipergrafía. (El gráfico de Gaifman (o gráfico primario o 2 secciones ) de una hipergrafía se forma agregando bordes entre dos vértices que aparecen juntos en alguna hiperedificación).
fuente