Abstrato

Polinômios Cromáticos

Karrie Williams

Quando se trata de colorir os nós de um grafo sob restrições específicas, existem muitas dificuldades fascinantes a explorar, que fornecem uma rápida visão geral dos fundamentos desta secção da teoria dos grafos. A coloração de um gráfico obtém-se atribuindo uma de um conjunto de cores a cada nó do gráfico. É uma tradução dos nós num (ou sobre) um conjunto s C em palavras mais formais (o conjunto de cores). Deixaremos de lado o debate sobre se os mapeamentos devem ser aplicados por enquanto. Uma coloração adequada de um grafo é aquela que cumpre a restrição de que os nós adjacentes não recebem (i.e., são mapeados) a mesma cor (elemento) de C. Uma coloração que não cumpre estes critérios é designada por coloração inadequada. Estes são os requisitos; no entanto, como estaremos quase sempre a lidar com colorações adequadas, será mais prático eliminar a palavra "própria" e concordar que quando dizemos "colorações" de um gráfico, queremos dizer "colorações adequadas", salvo indicação em contrário