Sobre quadrados mágicos, grafos graciosos e colorações especiais: teoremas, algoritmos e aplicações - Aires, Victória; de Freitas, Rosiane (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC), 2016)
Neste trabalho foram investigados problemas de rotulação em grafos, que consistem em atribuir rótulos, geralmente números inteiros, a vértices ou arestas, ou ambos, de modo a respeitar alguma restrição. Grafos rotulados incluem os grafos mágicos, grafos graciosos e colorações com restrições de distâncias. Quadrados mágicos podem ser modelados como grafos bipartidos completos, que por sua vez podem ter uma rotulação graciosa. Tal rotulação pode ser vista como um caso particular de coloração de vértices que respeita certa restrição de distância. Estas correlações foram exploradas nesta pesquisa, sendo reescritas em detalhes as provas dos principais teoremas, bem como implementados algoritmos de reconhecimento e determinação de soluções factíveis - exato e heurísticas gulosas, com uso do benchmark DIMACS. A prova da NP-completude para coloração com distâncias iguais é apresentada.