Qualquer coloração parcial dos vértices de um grafo define um conjunto
parcialmente ordenado cujos elementos são os menores obtidos por
contracção de arestas com extremos da mesma cor, no conjunto das
extensões cromáticas arbitrárias. A partir de cada um destes conjuntos
parcialmente ordenados e por aplicação do teorema da inversão Mobius,
determina-se o número de extensões cromáticas, o qual se concluiu ser um
polinómio na variável número de cores. Aplica-se esta abordagem na
modelação de problemas práticos, designadamente em problemas
combinatórios relacionados com o puzzle Sudoku (muito popular entre os
leitores de jornais e revistas), como é o caso do reconhecimento da
existência de solução (única ou não) em quadros com entradas
inicialmente preenchidas. Apresentam-se algumas questões em aberto
relacionadas com estes problemas e estendem-se os resultados obtidos à
determinação de polinómios cromáticos sem utilização da relação de
recorrência clássica de eliminação-contracção de arestas. |