Caracterizações e Reconhecimento de Grafos Bipartidos Cordiais

O estudo dos grafos bipartidos cordais foi motivado originalmente por suas aplicações em problemas de diversos contextos, como naqueles relacionados a matrizes não-simétricas, eliminação Gaussiana de matrizes, programação inteira e análise de matrizes. Tais estudos foram apresentados por diversos autores, tanto do ponto de vista teórico quanto prático. Os grafos bipartidos cordais são semelhantes aos grafos cordais em muitos aspectos. Os grafos cordais formam uma importante classe de grafos havendo inúmeros trabalhos a seu respeito.

Como os grafos cordais, os grafos bipartidos cordais são ricos em estrutura e muitos resultados originam-se de seu estudo. Sua importância está para a classe dos grafos bipartidos assim como a importância dos grafos cordais está para a classe dos grafos em geral.

O principal objetivo deste trabalho é realizar um estudo compreensivo da classe dos grafos bipartidos cordais, consolidando as caracterizações e algoritmos de reconhecimento mais eficientes existentes para esta classe em um único trabalho. Para tanto, é necessário conhecer a resolução de problemas relacionados a este problema, como a obtenção de ordenações lexicográficas duplas de matrizes, bem como suas soluções. As provas originais foram em sua maior parte reescritas de modo a obter uma padronização de notação em todo este trabalho.