Teses, Dissertações e Outros

Dado um grafo G=(V,E), uma coloração de arestas de G é uma atribuição de cores às arestas de G. Uma coloração total de um grafo G é 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. Além disso, t é o fator de extensão associado à árvore. O menor fator de extensão dentre todas as árvores geradoras de G é o índice de extensão de G, denotado por \sigma(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 \sigma=1, \sigma=2 ou \sigma=3. Sob esta nova perspectiva, classificamos completamente a classe dos grafos split com \sigma=2 com respeito à coloração de arestas e coloração total, restando apenas o estudo da subclasse com \sigma=3 para finalizar a classificação dos grafos split em ambos os problemas de coloração.