Teses, Dissertações e Outros

Dado um grafo G, uma coloração de arestas de G é uma atribuição de cores às arestas de G. Uma coloração total, por outro lado, é uma atribuição de cores que é realizada simultaneamente às arestas e aos vértices de G. Uma coloração é própria, quando cores distintas são atribuídas a elementos adjacentes e incidentes. O problema da coloração de arestas e o problema da coloração total têm como objetivo realizar a coloração própria de arestas/total de um grafo de modo que o número de cores utilizado seja minimizado. De maneira geral, estes problemas são NP-difíceis, o que incentiva a busca por classes onde seja possível resolvê-los em tempo polinomial. A classe dos grafos split é um exemplo de classe onde ambas as variantes permanecem em aberto. Chamamos de split um grafo cujo conjunto de vértices pode ser particionado em uma clique e um conjunto independente. Outro problema desafiador já estudado no contexto dos grafos split, é o problema da t-admissibilidade. Dado um grafo conexo G, uma árvore t-geradora de G é uma árvore geradora de G na qual a distância entre quaisquer dois vértices vizinhos em G é no máximo t. Se G admite tal árvore, G é dito t-admissível. O menor valor de t para o qual G é t-admissível é o índice de extensão de G, denotado por σ(G). O problema da t-admissibilidade consiste em determinar o índice de extensão de um grafo. Sabe-se que os grafos split são 3-admissíveis e que podemos particioná-los em três subclasses: grafos split com σ = 1, σ = 2 ou σ = 3. Sob esta nova perspectiva, classificamos completamente a classe dos grafos split com σ = 2 com respeito à coloração de arestas e coloração total, e também resolvemos estes dois problemas para uma subclasse dos grafos split com σ = 3..