Um Estudo das Estruturas de Grafos Sem Garras

Uma garra é um grafo bipartido composto por quatro vértices e três arestas, onde um vértice é adjacente a todos os outros. Um grafo é sem garras se ele não admite como subgrafo induzido a garra. Este trabalho descreve um estudo sobre a estrutura dos grafos sem garras. Inicialmente apresentamos os resultados desenvolvidos por Cl-ivátal e Sbihi sobre os grafos Berge e sem garras, onde baseados em um teorema de decomposição (todo grafo Berge e sem garras pode ser decomposto via corte-clique em dois tipos de grafos indecomponíveis, chamados elementar e peculiar), eles provam que o problema de reconhecimento desses tipos de grafos é resolvido em tempo polinomial. A estrutura dos grafos peculiares é completamente descrita pela sua definição porém o mesmo não acontece com os grafos elementares, então completando esse estudo, apresentamos os resultados desenvolvidos por Maffray e Reed que mostram uma caracterização dos grafos elementares, em termos de subgrafos proibidos e aumentação de um grafo linha de um multigrafo bipartido; produzindo assim uma descrição completa da estrutura dos grafos Berge e sem garras. A seguir apresentamos em linhas gerais os resultados recentes obtidos por Chudnovsky e Seymour sobre a estrutura dos grafos sem garras em geral.