Grafos Split e Grafos Split Generalizados

Este trabalho descreve um estudo sobre grafos split, grafos cujo conjunto de vértices pode ser particionado em um conjunto independente e uma clique e uma generalização dos grafos split, os grafos-(k,l), grafos onde o conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques. Como contribuição desta tese, apresentamos uma caracterização para a classe dos grafos cordais (2,1). Um grafo é dito cordal quando não possui subgrafos induzidos isomorfos a C_k, para k > 4.
Tratamos inicialmente de buscas em grafos, métodos sistemáticos e percorrer arestas. A seguir, apresentamos caracterizações e algoritmos de reconhecimento de grafos cordais e grafos split. Uma contribuição foi a de descrever com mais rigor e detalhe a demonstração do Teorema de Erdös-Gallai sobre sequências gráficas.
O resultado principal desta tese estabelece que as seguintes afirmações são equivalentes: Seja G um grafo cordal, (i) G é (2,1); (ii) G não contém dois triângulos isoladosç (iii) existe uma clique que intercepta todos os triângulos de G. A demonstração deste resultado é construtiva e conduz a um algoritmo de reconhecimento de grafos cordais (2,1) com complexidade O(mn), onde n e m representam, respectivamente, o número de vértices e arestas do grafo.