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 .
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.
Mi pregunta es, ¿qué tal el color de los gráficos planos , o más generalmente, el color para C ≥ 2 ?
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 .