Nesta tese de doutoramento são considerados três problemas em grafos,

para os quais são obtidos resultados quando a entrada é restrita a

algumas classes. Todos os problemas são problemas de otimização

combinatória sobre grafos simples e apresentam diferentes

classificações de complexidade. Em dois casos, o estudo focou classes

de grafos com ``poucos P4's'' e o uso da decomposição modular. No

último caso, considerou-se uma subclasse dos grafos de intervalos e a

aplicação de uma técnica conhecida como pullback.

O primeiro problema estudado é o Problema dos Separadores Minimais,

para o qual são conhecidos algoritmos polinomiais em toda classe de

grafos que possuir um número polinomial de separadores minimais. Serão

dados, como contribuição deste trabalho, um algoritmo linear para

listar os separadores minimais de grafos P4-carregados estendidos e

limitantes justos no número e tamanho dos separadores minimais destes

grafos, bem como de algumas de suas subclasses, P4-carregada,

P4-arrumada e P4-leve. Estes resultados estendem um algoritmo anterior

para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de

grafos entre as que possuem um número de separadores minimais limitado

por um função linear no número de vértices do grafo.

Em seguida, será tratado o Problema de Empacotamento de Cliques, uma

extensão do problema de emparelhamento máximo. Para a maioria das

classes de grafos mais importantes, o problema é NP-Difícil. A

contribuição apresentada resolve este problema em tempo polinomial

(para qualquer tamanho fixo de clique) em grafos P4-arrumados, através

de uma técnica similar a utilizada para os cografos. Infelizmente,

para as superclasses mais estudadas da classe P4-arrumada, este

problema é NP-Difícil, o que é um indício de que a técnica utilizada

foi totalmente aproveitada em relação às classes com poucos P4's.

Por fim, será estudado o Problema da Coloração Total Forte, uma

variação do problema clássico da coloração total, que foi introduzido

há pouco tempo e ainda tem sua complexidade computacional

desconhecida. Como esperado, existem algoritmos polinomiais apenas

para classes bastante simples de grafos. Além da complexidade, outro

importante ponto em aberto para o problema é a conjectura de que o

número de cores necessárias na solução do problema para um grafo G

seria limitado por Delta(G) + 3. A técnica do pullback, já utilizada

para os Problemas de Coloração de Arestas e Coloração Total em grafos

dualmente cordais será estendida, resultando em um algoritmo linear

para grafos indiferença (também conhecido como grafos de intervalos

próprios). Este algoritmo produz uma solução que valida a conjectura

nesta classe de grafos.

Estas contribuições confirmam a importância da decomposição modular em

algoritmos para classes de grafos com ``poucos P4's'' e ampliam o uso

da técnica do pullback para variações dos problemas clássicos de

coloração.