O Programa de Pós-Graduação em Matemática e Estatística convida a comunidade acadêmica a participar da palestra intitulada: “
Resumo: Na literatura, as classes de grafos mais estudadas são as dos grafos bipartidos, cordais, splits, árvores, cografos, cliques, planares, etc. Problemas em grafos são problemas que vão desde o reconhecimento se um dado grafo pertence a uma classe, enunciados de teoremas de caracterização da classe, até a determinação de parâmetros que são valores numéricos referentes às características inerentes do próprio grafo. Por exemplo, o problema de colorir um grafo, ou problema da coloração, é o problema de determinar o menor número de cores que podemos colorir os vértices de um grafo de modo que vértices adjacentes recebam sempre atribuições de cores diferentes. Esse menor número de cores é um parâmetro chamado número cromático do grafo. O Problema da coloração considerado para uma classe de grafo qualquer é um problema combinatório ainda em aberto na Matemática e de computação muito difícil. Os problemas combinatórios que podem ser resolvidos por um algoritmo polinomial formam a chamada classe P de problemas computacionais. No entanto, para alguns problemas combinatórios não é conhecido, até a presente data, nenhum algoritmo de tempo polinomial que resolva esses problemas difíceis. Quem encontrar algum algoritmo de tempo de execução polinomial que resolva algum destes problemas difíceis, resolverá a questão em aberto mais famosa da Computação,P = NP? ,além de ficar milionário. Nesta palestra, buscamos debater, em maiores detalhes, os referidos assuntos a nível do estado da arte, bem como divulgar a área de Algoritmos e Combinatória.