|
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 perfeitosAlguns dos mais conhecidos grafos perfeitos são
Referências
|
