Teorema do gráfico perfeito forte - Strong perfect graph theorem

Em teoria gráfico , a forte gráfico perfeito teorema é uma caracterização gráfico proibido dos gráficos perfeitos como sendo exactamente os gráficos que têm buracos nem ímpares (ímpar de comprimento ciclos induzidos ) nem antiholes ímpares (complementos de furos ímpares). Foi conjecturado por Claude Berge em 1961. Uma prova de Maria Chudnovsky , Neil Robertson , Paul Seymour e Robin Thomas foi anunciada em 2002 e publicada por eles em 2006.

A prova do teorema do gráfico perfeito forte rendeu aos seus autores um prêmio de US $ 10.000 oferecido por Gérard Cornuéjols, da Carnegie Mellon University, e o Prêmio Fulkerson de 2009 .

Demonstração

Um gráfico perfeito é um gráfico no qual, para cada subgrafo induzido , o tamanho do clique máximo é igual ao número mínimo de cores em uma coloração do gráfico; Os gráficos perfeitos incluem muitas classes de gráfico conhecidas, incluindo os gráficos bipartidos , gráficos de cordas e gráficos de comparabilidade . Em seus trabalhos de 1961 e 1963 definindo pela primeira vez esta classe de gráficos, Claude Berge observou que é impossível para um gráfico perfeito conter um orifício ímpar, um subgrafo induzido na forma de um gráfico de ciclo de comprimento ímpar de cinco ou mais, porque os buracos ímpares têm clique número dois e número cromático três. Da mesma forma, ele observou que grafos perfeitos não podem conter anti-furos ímpares, subgráficos induzidos complementares aos furos ímpares: um anti-furo ímpar com 2 k  + 1 vértices tem número de clique k e número cromático k  + 1, o que é novamente impossível para grafos perfeitos. Os gráficos sem furos ou anti-furos estranhos ficaram conhecidos como gráficos de Berge.

Berge conjecturou que todo gráfico de Berge é perfeito ou, de maneira equivalente, que os gráficos perfeitos e os gráficos de Berge definem a mesma classe de gráficos. Isso ficou conhecido como conjectura do gráfico perfeito forte, até sua prova em 2002, quando foi renomeado teorema do gráfico perfeito forte.

Relação com o teorema do gráfico perfeito fraco

Outra conjectura de Berge, comprovada em 1972 por László Lovász , é que o complemento de todo gráfico perfeito também é perfeito. Isso ficou conhecido como teorema do gráfico perfeito , ou (para distingui-lo da conjectura / teorema do gráfico perfeito forte) o teorema do gráfico perfeito fraco. Como a caracterização de gráfico proibida de Berge é autocomplementar, o teorema do gráfico perfeito fraco segue imediatamente do teorema do gráfico perfeito forte.

Ideias de prova

A prova do teorema do gráfico perfeito forte por Chudnovsky et al. segue um esboço conjecturado em 2001 por Conforti, Cornuéjols, Robertson, Seymour e Thomas, segundo o qual cada gráfico de Berge forma um dos cinco tipos de bloco de construção básico (classes especiais de gráficos perfeitos) ou tem um dos quatro tipos diferentes de decomposição estrutural em gráficos mais simples. Um gráfico de Berge minimamente imperfeito não pode ter nenhuma dessas decomposições, de onde se segue que nenhum contra-exemplo para o teorema pode existir. Essa ideia foi baseada em decomposições estruturais conjecturadas anteriores de tipo semelhante que teriam implicado a conjectura do grafo perfeito forte, mas acabou sendo falsa.

As cinco classes básicas de grafos perfeitos que formam o caso base desta decomposição estrutural são os grafos bipartidos , grafos de linha de grafos bipartidos, grafos complementares de grafos bipartidos, complementos de grafos de linha de grafos bipartidos e grafos de divisão dupla. É fácil ver que os grafos bipartidos são perfeitos: em qualquer subgrafo induzido não trivial, o número do clique e o número cromático são dois e, portanto, iguais. A perfeição de complementos de grafos bipartidos e de complementos de gráficos de linha de grafos bipartidos, são ambos equivalente a teorema de König relacionando os tamanhos de matchings máximo , conjuntos máximas independentes e coberturas mínimas de vértice em grafos bipartidos. A perfeição dos grafos lineares dos grafos bipartidos pode ser afirmada de forma equivalente ao fato dos grafos bipartidos possuírem índice cromático igual ao seu grau máximo , comprovado por Kőnig (1916) . Portanto, todas as quatro classes básicas são perfeitas. Os gráficos de divisão dupla são relativos aos gráficos de divisão que também podem ser mostrados como perfeitos.

Os quatro tipos de decomposição considerados nesta prova são 2-joins, complementos de 2-joins, partições enviesadas balanceadas e pares homogêneos.

Uma junção 2 é uma partição dos vértices de um grafo em dois subconjuntos, com a propriedade de que as arestas que medem o corte entre esses dois subconjuntos formam dois grafos bipartidos completos separados por vértices . Quando um gráfico tem uma junção 2, ele pode ser decomposto em subgráficos induzidos chamados "blocos", substituindo um dos dois subconjuntos de vértices por um caminho mais curto dentro desse subconjunto que conecta um dos dois grafos bipartidos completos ao outro; quando esse caminho não existe, o bloco é formado pela substituição de um dos dois subconjuntos de vértices por dois vértices, um para cada subgrafo bipartido completo. Uma junção 2 é perfeita se e somente se seus dois blocos forem perfeitos. Portanto, se um grafo minimamente imperfeito tem uma junção 2, ele deve ser igual a um de seus blocos, de onde se segue que deve ser um ciclo ímpar e não Berge. Pela mesma razão, um grafo minimamente imperfeito cujo complemento tem uma junção 2 não pode ser Berge.

Uma partição enviesada é uma partição dos vértices de um gráfico em dois subconjuntos, um dos quais induz um subgrafo desconectado e o outro possui um complemento desconectado; Chvátal (1985) conjeturou que nenhum contra-exemplo mínimo para a conjectura do gráfico perfeito forte poderia ter uma partição enviesada. Chudnovsky et al. introduziu algumas restrições técnicas nas partições de inclinação e foram capazes de mostrar que a conjectura de Chvátal é verdadeira para as "partições de inclinação equilibradas" resultantes. A conjectura completa é um corolário do teorema do gráfico perfeito forte.

Um par homogêneo está relacionado a uma decomposição modular de um gráfico. É uma partição do gráfico em três subconjuntos V 1 , V 2 e V 3, de modo que V 1 e V 2 juntos contêm pelo menos três vértices, V 3 contém pelo menos dois vértices e para cada vértice v em V 3 e cada i em {1,2} ou v é adjacente a todos os vértices em V i ou a nenhum deles. Não é possível que um gráfico minimamente imperfeito tenha um par homogêneo. Após a prova da conjectura do grafo perfeito forte, Chudnovsky (2006) a simplificou ao mostrar que pares homogêneos poderiam ser eliminados do conjunto de decomposições usado na prova.

A prova de que todo grafo de Berge cai em uma das cinco classes básicas ou tem um dos quatro tipos de decomposição segue uma análise de caso, de acordo com a existência de certas configurações dentro do gráfico: uma "maca", um subgrafo que pode ser decomposto em três caminhos induzidos sujeitos a certas restrições adicionais, o complemento de uma maca e uma "roda adequada", uma configuração relacionada a um gráfico de roda , consistindo em um ciclo induzido junto com um vértice de cubo adjacente a pelo menos três vértices de ciclo e obedecendo a vários restrições adicionais. Para cada escolha possível de se uma maca ou seu complemento ou uma roda própria existe dentro do dado gráfico Berge, o gráfico pode ser mostrado em uma das classes básicas ou ser decomposto. Esta análise de caso completa a prova.

Notas

Referências

links externos