Decomposição por Cliques Maximais e Subgrafos Proibidos para Grafos de Caminho

Caracterizações de classes de grafos por subgrafos ou minors proibidos são  encontradas em diversas áreas da Teoria dos Grafos. Tais caracterizações implicam em diversas propriedades estruturais da classe em questão e, muitas vezes, dão origem a algoritmos eficientes para problemas que são difíceis em geral. As classes de grafos de caminho, isto é, as classes de grafos de interseção de caminhos em árvores, são passíveis de caracterizações por subgrafos proibidos, mas para muitas delas estas caracterizações ainda não são conhecidas.
 Nesta dissertação, estudamos alguns aspectos das caracterizações por proibição. No caso geral, investigamos a existência destas caracterizações em conjuntos quasiordenados, quando certas propriedades especiais são exigidas. No caso dos grafos, analisamos uma ferramenta utilizada para encontrar tais caracterizações, chamada decomposição de grafos, e elaboramos um algoritmo para decomposição por cliques maximais separadoras, que se aplica na busca de subgrafos proibidos para grafos de caminho. Finalmente, aplicamos técnicas já conhecidas, em conjunto com uma nova ferramenta introduzida neste trabalho, para encontrar algumas famílias infinitas de subgrafos proibidos para as classes de grafos de caminho DE e UE-Cordal.