Coloração total semiforte

Resumo

Este é um projeto de pesquisa para a solicitação de uma bolsa de mestrado para Atílio Gomes Luiz. Propõe-se a investigação de um tipo especial de coloração total, denominada coloração total semiforte. Dada uma coloração total, rotula-se cada vértice do grafo com o conjunto formado pela cor do vértice e pelas cores das arestas que nele incidem. Uma coloração total é semiforte quando os rótulos de vértices adjacentes são distintos. O menor número de cores para o qual um grafo admite uma coloração total semiforte é denominado número cromático total semiforte. Pouco se conhece sobre o problema de se determinar o número cromático total semiforte: está determinado para poucas famílias de grafos, mas a complexidade do problema é desconhecida. No artigo seminal desta coloração, os autores conjeturam que o número cromático total semiforte de um grafo simples é no máximo o seu grau máximo mais três unidades. Neste projeto, pretendemos verificar a conjetura citada para os grafos de algumas classes e, se possível, determinar o número cromático total semiforte desses grafos.