Una coloración plana inadecuada con un tamaño de componente monocromático

11

Relajemos un poco el color, es decir, permitimos que se asigne el mismo color a un pequeño número de vértices adyacentes. Un componente monocromático se define como un componente conectado en el subgrafo inducido por el conjunto de vértices que reciben el mismo color, y la pregunta es pedir el número mínimo de colores necesarios para colorear un gráfico de manera que el componente monocromático más grande tenga tamaño no más de C . λC
La coloración tradicional puede considerarse como coloración en esta configuración. Por lo tanto, encontrar el número mínimo de λ es NP-duro para el gráfico plano en general. [λ,1]λ

Mi pregunta es, ¿qué tal el color de los gráficos planos[λ,2] , o más generalmente, el color para C 2 ?[λ,C]C2

Esto puede ser visto como un doble problema de lo que se estudia por Edwards y Farr , donde es fijo, y uno se pregunta para encontrar el tamaño mínimo de C .λC

Yixin Cao
fuente

Respuestas:

3

La coincidencia perfecta de 2 colores en gráficos planos cúbicos es muy similar a su problema, que Schaefer declaró que era NP completo en su famoso documento de teorema de dicotomía, aunque no dio la prueba de los gráficos planos cúbicos. El problema requiere la existencia de dos colores de gráficos planos cúbicos de manera que cada vértice tenga exactamente un vecino del mismo color que él.

EDITAR: la coloración defectuosa es la versión de decisión de su problema. Un gráfico es (k, d) -colorable si uno puede colorear los vértices con k colores de manera que ningún vértice sea adyacente a más de d vértices de su mismo color. Se demostró que el problema de decisión (2,1), la coloración con defectos, que es equivalente a su problema de optimización, era NP completo incluso para gráficos planos .

Mohammad Al-Turkistany
fuente
¿Qué es una reducción de la "coincidencia perfecta de 2 colores en gráficos planos cúbicos" al problema de Yixin?
La combinación perfecta de 2 colores es un caso especial donde el tamaño máximo de componente conectado es exactamente igual a C.
Mohammad Al-Turkistany
Gracias por su respuesta, pero no puedo estar de acuerdo con usted. Como en el problema de la "coincidencia perfecta de 2 colores en gráficos planos cúbicos", CADA componente debe ser exactamente 2. Pero mi pregunta parece más fácil.
Yixin Cao
Sí, perdí esa diferencia.
Mohammad Al-Turkistany