Uma coloração de vértices própria de um grafo G é uma atribuição de cores aos vértices de G de forma que vértices adjacentes tenham cores distintas. Uma coloração harmoniosa de um grafo G é uma coloração própria de seus vértices tal que
todo par possível de cores apareça como extremos de no máximo uma aresta. Chamamos de número cromático harmonioso o menor número de cores necessárias para um grafo ter uma coloração harmoniosa. Neste seminário será apresentado este problema, alguns resultados e limitantes.

O Another Solution Problem (ASP) de um problema P é descrito como: dados uma instância x de P e uma solução s para ela, encontre uma solução para x diferente de s. Neste seminário serão apresentados conceitos de ASP-completude e reduções ASP. Também serão apresentadas aplicações de ASP-completude para provar NP-completude de três famosos puzzles: Slither Link (Voltas e Cercas), Cross Sum (Kakuro) e Number Place (Sudoku).