Grafo perfeito

Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo.

Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2.

Grafos perfeitos incluem muitas famílias importantes de grafos, e servem para unificar os resultados relativos a colorações e cliques nessas famílias. Por exemplo, em todos os grafos perfeitos, o problema da coloração de grafos, o problema da clique máxima e o problema do conjunto independente máximo podem ser resolvidos em tempo polinomial^[1]. Além disso, vários teoremas importantes min-max em análise combinatória, como o teorema de Dilworth, podem ser expressos em termos da perfeição de alguns grafos associados.

A teoria dos grafos perfeitos desenvolveu-se a partir um resultado de 1958 de Tibor Gallai que em linguagem moderna, pode ser interpretado como indicando que o complementar de um grafo bipartido é perfeito; este resultado também pode ser visto como um simples equivalente do teorema de König, um resultado bem mais anterior relacionando acoplamentos e coberturas de vértices em grafos bipartidos. O primeiro uso da expressão "grafo perfeito" parece estar em um artigo de 1963 de Claude Berge. Neste artigo ele unificou o resultado de Gallai com vários resultados semelhantes através da definição de grafos perfeitos e conjecturando uma caracterização destes grafos que mais tarde foi comprovado como o Teorema Forte dos Grafos Perfeitos.

Familias de grafos que são perfeitos

Alguns dos mais conhecidos grafos perfeitos são

• grafos bipartidos
• Os grafos de linha de grafos bipartidos (ver teorema de König)
• grafos de intervalos (vértices representam intervalos de linha; e arestas, seus pares de interseções não vazias)
• grafos cordais (cada ciclo de quatro ou mais vértices tem uma corda, que é uma aresta entre dois nós que não são adjacentes no ciclo)
• grafos distância-hereditários
• grafos de permutação
• grafos de comparabilidade (um vértice por elemento em uma ordem parcial, e uma aresta entre quaisquer dois elementos comparáveis)
• grafos roda com número ímpar de vértices
• grafos divididos (grafos que podem ser particionados em um clique e um conjunto independente)
• grafos perfeitamente ordenáveis (grafos que podem ser ordenados de tal forma que um algoritmo de coloração gananciosa é ótimo em todo subgrafo induzido)

Referências