Abstracto

Polinomios cromáticos

Karrie Williams

Cuando se trata de colorear los nodos de un grafo bajo restricciones particulares, hay muchas dificultades fascinantes para explorar que proporcionan una rápida descripción general de los conceptos básicos de esta sección de la teoría de grafos. La coloración de un grafo se logra asignando uno de un conjunto de colores a cada nodo en el grafo. Es una traducción de los nodos en (o sobre) un conjunto s C en palabras más formales (el conjunto de colores). Dejaremos de lado el debate sobre si las asignaciones deben ser en cualquiera de los dos sobre por el momento. Una coloración adecuada de un grafo es aquella que cumple con la restricción de que los nodos adyacentes no se asignan (es decir, se asignan sobre) el mismo color (elemento) de C. Una coloración que no cumple con estos criterios se conoce como coloración inapropiada. Estos son los requisitos; sin embargo, debido a que casi siempre trataremos con coloraciones adecuadas, será más práctico eliminar la palabra "adecuada" y aceptar que cuando decimos "coloraciones" de un grafo, nos referimos a "coloraciones adecuadas" a menos que se indique lo contrario.