Es bien sabido que los polinomios cromáticos cuentan coloraciones que difieren por permutaciones de colores. ¿Qué se sabe de sus análogos que no cuentan tales coloraciones como distintas?
Respuesta
¿Demasiados anuncios?
zyx
Puntos
20965
Hasta el isomorfismo hay un número finito de coloraciones, por lo que no existe ninguna función de recuento polinómica (o ilimitada) si se permite el reetiquetado arbitrario de los colores.
Probablemente se refería a la permutación de la realmente utilizado colores dentro de cada coloración. Pero aquí la interpretación de "permutación" no es única. Hay permutaciones de la $k$ colores utilizados (hay algunos $G$ -para esto, similar a la sustitución de las funciones generadoras ordinarias por funciones generadoras exponenciales), permutaciones de la $k$ utilizó colores que son inducidos por automorfismos del grafo, y tal vez alguna ponderación del primer tipo de permutaciones utilizando la acción de los automorfismos (como en la fórmula de Wick). Además, sin pensarlo bien, podría ser necesario distinguir entre los automorfismos del grafo y los automorfismos de la partición del grafo determinada por la coloración.
Así que supongo que o bien quieres una versión del polinomio cromático que tenga en cuenta los automorfismos, o bien algún polinomio transformado que contenga la misma información que el polinomio cromático.
