Data: 08/10/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Partição de Arestas em Cliques em Grafos (k,l)
Palestrante: Átila Arueira Jones (IFSMG - Juiz de Fora)


Resumo: O problema de edge clique partition consiste em particionar o conjunto de arestas de um grafo em cliques induzidas pelas arestas. Dentre todas as partições possíveis, denotamos a cardinalidade mínima de uma partição por cp(G). Este problema já é conhecido como NP-completo para grafos em geral, inclusive para split, grafos livres de K_4 e os grafos cordais. Provamos neste trabalho que a NP-completude é mantida para a classe dos grafos 3-coloríveis, subclasse dos grafos livres de K_4. Além disso, estabelecemos a complexidade do problema para grafos (k,l), aqueles cujo conjunto de vértices pode ser particionado em k independentes e l cliques, estabelecendo quando o problema é NP-completo ou polinomial para cada k e l fixados.