Decomposition by maximal cliques and forbidden subgraphs for path graphs - Nobrega, Hugo de H. C.; Cerioli, Márcia R.; Viana, Jorge Petrúcio (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2012: Anais do XXV Concurso de Teses e Dissertações, 2012)
Neste trabalho, 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 de grafos, nós elaboramos um algoritmo para decomposição por cliques maximais separadoras, que se aplica na busca de subgrafos proibidos para algumas classes de grafos de caminho. Finalmente, aplicamos técnicas já conhecidas, em conjunto com uma nova ferramenta introduzida neste trabalho, para encontrar uma família infinita de subgrafos proibidos para a classe de grafos de caminho UE.