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. 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)
Perfeito