Defesa de Tese de Doutorado: Sheila Morais de Almeida
Coloração de Arestas em Grafos Split.
| What | Defesa de Doutorado |
|---|---|
| When |
28/03/2012 from 09:00 to 13:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
|
Uma k-coloração de arestas em um grafo G é uma atribuição de k cores para as arestas de G tal que arestas incidentes em um mesmo vértice têm cores distintas. O índice cromático de G é o menor k para o qual G possui uma k-coloração de arestas e é denotado por χ'(G). Por definição, χ'(G) ≥ Δ(G), onde Δ(G) é o grau máximo de G. Em 1964, Vizing provou que, para qualquer grafo simples G, χ'(G) ≤ Δ(G) + 1, dando origem ao Problema da Classificação, que consiste em decidir, dado um grafo G, se χ'(G) = Δ(G) ou χ'(G) = Δ(G) + 1. No primeiro caso, dizemos que G é Classe 1, caso contrário, G é Classe 2. Em 1981, Holyer mostrou que decidir se um grafo é Classe 1 é NP-completo. Em 1991, Cai e Ellis demonstraram que decidir se um grafo é Classe 1 continua NP-completo mesmo quando restrito a algumas classes de grafos, tais como os grafos perfeitos. Restringindo-se aos grafos perfeitos, nestes últimos 15 anos, até aonde vai o nosso conhecimento, somente os multipartidos completos e os split-indiferença foram inteiramente classificados. Resultados parciais foram obtidos para algumas classes de grafos, como os duplamente cordais com Δ ímpar e os split com Δ ímpar, que são Classe 1. Uma conseqüência da classificação dos grafos duplamente cordais com Δ ímpar foi a classificação dos grafos fortemente cordais, de intervalos e indiferença com grau máximo ímpar - todos subclasses dos grafos duplamente cordais. Uma condição suficiente para que um grafo G seja Classe 2 é garantir a desigualdade m > Δ(G) * ën/2û, onde m e n representam o número de arestas e de vértices de G, respectivamente. Nesse caso, G é chamado de sobrecarregado. Se um grafo G possui um subgrafo H com Δ(H) = Δ(G) e H é sobrecarregado, então G é chamado subgrafo-sobrecarregado e também é Classe 2. Esta tese apresenta um estudo sobre a coloração de arestas em grafos split, com novos resultados sobre a classificação de grafos split com grau máximo par. Entre os grafos split com Δ par, sabe-se que alguns são subgrafo-sobrecarregados e que, portanto, nem todo grafo split com grau máximo par é Classe 1. Por outro lado, não se conhece nenhum grafo split com grau máximo par que seja Classe 2 e não seja subgrafo-sobrecarregado. Neste trabalho, são apresentadas algumas técnicas com as quais se obtém uma Δ-coloração de arestas em alguns subconjuntos de grafos split com grau máximo par e é dada uma caracterização estrutural dos grafos split que são subgrafo-sobrecarregados.
