Considerar (correcto) para colorear de un número finito de gráfico de $G$ con exactamente $n$ colores y el siguiente para colorear de transformación: seleccione un borde de la gráfica con los nodos finales de colores $a$ e $b$ e intercambiar los colores de $a$ e $b$ en el componente conectado de la gráfica, que contiene el borde y color con los dos colores. El resultado es un nuevo (correcto) para colorear de la gráfica. Permite llamar a dos colorantes equivalente, si hay una secuencia de los swaps de tomar una gráfica colorante en otro. Deje $C_n(G)$ ser un número máximo de no equivalente y el color de la gráfica de $G$ con $n$ colores (número de clases de equivalencia).
PREGUNTAS:
- Es $C_n(G)$ un nuevo gráfico invariantes o puede ser calculado a partir de la cromática polinomio de la gráfica de $G$?
- Es allí eficiente forma para calcular el $C_n(G)$?
- Podría $C_n(G)$ ser un grafo completo de todos los idiomas, teniendo en cuenta que para todos los números naturales $n$?
NOTA:
Para los que no la banalidad y el origen de $C_n(G)$, por favor, consulte En el cuatro y cinco de color teoremas
