Grafos Perfeitos
Conforme já discutido, um número cromático alto pode ocorrer como um fenômeno puramente global: mesmo quando um grafo tem uma circunferência grande e, portanto, se parece localmente com uma árvore, seu número cromático pode ser arbitrariamente alto. Como essa 'dependência global' é obviamente difícil de lidar, pode-se interessar por grafos onde esse fenômeno não ocorre, ou seja, cujo número cromático é alto apenas quando há uma razão local para isso.
Antes de tornar isso preciso, vamos definir duas novas invariantes para um grafo $G$. O maior inteiro $r$ tal que $K^r \subseteq G$ é o número clique $\omega (G)$ de $G$, e o maior inteiro $r$ tal que $\overline{K^r} \subseteq G$$ (induzido) é o número de independência $\alpha (G)$ de $G$ . Claramente, $\alpha (G) = \omega (\overline{G})$ e $\omega (G) = \alpha (\overline{G})$.
Um grafo é dito perfeito se todo subgrafo induzido $H \subseteq G$ tem número cromático $\chi (H) = \omega (H)$, ou seja, se o limite inferior trivial de $\omega (H)$ cores sempre é suficiente para colorir os vértices de $H$. Assim, ao provar uma afirmação da forma $\chi (G) > k$ em geral pode ser difícil, mesmo em princípio, para um dado grafo $G$, isso sempre pode ser feito para um grafo perfeito simplesmente exibindo algum $K^{k+1}$ subgrafo como um 'certificado' de não colorabilidade com $k$ cores.
À primeira vista, a estrutura da classe dos grafos perfeitos parece um tanto artificial: embora seja fechado sob subgrafos induzidos (mesmo que apenas por definição explícita), não é fechado sob subgrafos ou supergrafos gerais, muito menos minors. No entanto, a perfeição é uma noção importante na teoria dos grafos: o fato de várias classes fundamentais de grafos serem perfeitas (como por acaso) pode servir como uma indicação superficial disso. (A classe do grafo perfeito tem propriedades de dualidade com conexões profundas com a otimização e a teoria da complecidade, que estão longe de serem compreendidas.)
Quais grafos, então, são perfeitos? Grafos bipartidos são, por exemplo. Menos trivialmente, os complementos de grafos bipartidos também são perfeitos, um fato equivalente ao teorema de dualidade de König. Os chamados grafos de comparabilidade são perfeitos, assim como os grafos de intervalos; ambos aparecem em inúmeras aplicações.
A fim de estudar pelo menos um desses exemplos com algum detalhe, provamos aqui que os grafos cordais são perfeitos: um grafo é cordal (ou triangulado) se cada um de seus ciclos de comprimento pelo menos $4$ tiver uma corda, ou seja, se não contiver ciclos induzidos que não sejam triângulos.
Para mostrar que os grafos cordais são perfeitos, primeiro caracterizaremos sua estrutura. Se $G$ é um grafo com subgrafos induzidos $G_1,G_2$ e $S$, tais que $G = G_1 \cup G_2$ e $S = G_1 \cap G_2$ , dizemos que $G$ surge de $G_1$ e $G_2$ colando esses grafos juntos ao longo de $S$.
Proposição 1
Um grafo é cordal se, e somente se, ele pode ser construído recursivamente colando subgrafos completos, começando de grafos completos.
Demonstração:
Se $G$ é obtido de dois grafos cordais $G_1,G_2$, G colando-os juntos ao longo de um subgrafo completo, então $G$ é claramente novamente cordal: qualquer ciclo induzido em $G$ está em $G_1$ ou $G_2$ e, portanto, é um triângulo por suposição. Uma vez que os grafos completos são cordais, isso prova que todos os grafos construíveis conforme declarado são cordais.
Reciprocamente, seja $G$ um grafo cordal. Mostramos por indução em $|G|$ que $G$ pode ser construído como descrito. Isso é trivial se $G$ for completo. Portanto, assumimos que $G$ não é completo, em particular $|G| > 1$, e que todos os grafos cordais menores são construíveis conforme declarado. Seja $a,b \in G$ dois vértices não adjacentes, e seja $X \subseteq V(G) \setminus \{a,b\}$ um $a-b$ separador mínimo. Deixe $C$ denotar o componente de $G-X$ contendo $a$, e coloque $G_1 := G[V(C) \cup X]$ e $G_2 := G-C$. Então $G$ surge de $G_1$ e $G_2$ colando esses grafos juntos ao longo de $S := G[X]$.
Uma vez que $G_1$ e $G_2$ são cordais (sendo subgrafos induzidos de $G$) e portanto construíveis por indução, basta mostrar que $S$ é completo. Suponha, então, que $s,t \in S$ não sejam adjacentes. Pela minimalidade de $X = V(S)$ como um $a-b$ separador, tanto $s$ quanto $t$ têm um vizinho em $C$. Portanto, existe um $X$-caminho de $s$ para $t$ em $G_1$; deixamos $P_1$ ser um tal caminho mais curto. Analogamente, $G_2$ contém um $X$-caminho mais curto $P_2$ de $s$ a $t$. Mas então $P_1 \cap P_2$ é um ciclo sem corda de comprimento $ \geq 4$, contraindo nossa suposição de que $G$ é cordal.
Proposição
Todo grafo cordal é perfeito.
Demonstração:
Como grafos completos são perfeitos, basta pela Proposição $1$ acima mostrar que qualquer grafo $G$ obtido a partir de grafos perfeitos $G_1,G_2$ colando-os juntos ao longo de um subgrafo completo $S$ é novamente perfeito. Portanto, seja $H \subseteq G$ um subgrafo induzido; mostramos que $\chi (H) \leq \omega(H)$.
Faça $H_i := H \cap G_i$ para $i=1,2$ , e deixe $T := H \cap S$. Então $T$ é novamente completo, e $H$ surge de $H_1$ e $H_2$ colando ao longo de $T$. Como um subgrafo induzido de $G_i$, cada $H_i$ pode ser colorido com $\omega (H_i)$ cores. Uma vez que $T$ é completo e, portanto, colorido injetivamente, duas dessas colorações, uma de $H_1$ e uma de $H_2$, podem ser combinadas em uma coloração de $H$ com $max \{ \omega (H_1), \omega (H_2)\} \leq \omega (H)$ cores, se necessário, permutando as cores em um dos $H_i$.
Por definição, todo subgrafo induzido de um grafo perfeito é novamente perfeito. A propriedade de perfeição pode, portanto, ser caracterizada por subgrafos induzidos proibidos: existe um conjunto $\mathcal{H}$ de grafos imperfeitos tal que qualquer grafo é perfeito se, e somente se, não possui subgrafo induzido isomórfico a um elemento de $\mathcal{H}$. (Por exemplo, podemos escolher como $\mathcal{H}$ o conjunto de todos os grafos imperfeitos com vértices em $\mathbb{N}$.)
Naturalmente, gostaríamos de manter $\mathcal{H}$ o menor possível. É um dos resultados mais profundos da teoria dos grafos que $\mathcal{H}$ precisa conter apenas dois tipos de grafos: os ciclos ímpares de comprimento $\geq 5$ e seus complementos. Nenhum deles é perfeito, como visto no Teorema de Lovász mais a frente. Este fato, a famosa conjectura do grafo perfeito forte de Berge, foi provado apenas muito recentemente:
Teorema (Chudnovsky, Robertson, Seymour & Thomas)
Um grafo $G$ é perfeito se, e somente se, nem $G$ nem $\overline{G}$ contém um ciclo ímpar de tamanho pelo menos $5$ como um subgrafo induzido.
No contexto de grafos perfeitos, ciclos induzidos de comprimento de pelo menos $5$ em $G$ são geralmente referidos como buracos em $G$, enquanto buracos em $\overline{G}$ são antiburacos de $G$. Nesse jargão, o teorema do grafo perfeito forte diz que um grafo é perfeito se, e somente se, não tiver buracos nem antiburacos.
A prova do teorema do grafo perfeito forte é longa e técnica, e não seria muito esclarecedor tentar esboçá-la. Para lançar mais luz sobre a noção de perfeição, damos duas provas diretas de sua consequência mais importante: o teorema do grafo perfeito, anteriormente a conjectura do grafo perfeito fraco de Berge:
Teorema (Lovász)
Um grafo é perfeito se, e somente se, seu complemento é perfeito.
A primeira prova que damos para o Teorema de Lovász é a prova original de Lovász, que ainda é insuperável em sua clareza e quantidade de 'sensação' do problema que transmite. Nossa segunda prova, devido a Gasparian, é uma elegante prova de álgebra linear de outro teorema de Lovász enunciado e demonstrado mais a frente, que facilmente implica o teorema acima.
Preparemos nossa primeira prova do Teorema por meio de um lema. Seja $G$ um grafo e $x \in G$ um vértice, e seja $G'$ obtido de $G$ adicionando um vértice $x'$ e unindo-o a $x$ e todos os vizinhos de $x$. Dizemos que $G'$ é obtido de $G$ expandindo o vértice $x$ para uma aresta $xx'$.
Lema
Qualquer grafo obtido de um grafo perfeito pela expansão de um vértice é novamente perfeito.
Demonstração:
Usamos indução na ordem do grafo perfeito considerado. Expandir o vértice de $K^1$ produz $K^2$, que é perfeito. Para o passo de indução, seja $G$ um grafo perfeito não trivial , e seja $G'$ obtido de $G$ expandindo um vértice $x \in G$ para uma aresta $xx'$. Para nossa prova de que $G'$ é perfeito basta mostrar $\chi (G') \leq \omega (G')$: todo subgrafo induzido próprio $H$ de $G'$ é isomórfico a um subgrafo induzido de $G$ ou obtido de um subgrafo induzido adequado de $G$ pela expansão de $x$; em ambos os casos, $H$ é perfeito por suposição e hipótese de indução e, portanto, pode ser colorido com $\omega (H)$ cores.
Seja $\omega (G) =: \omega$; então $\omega (G') \in \{\omega, \omega +1\}$. Se $\omega (G') = \omega +1$, então
$$\chi (G') \leq \chi (G) +1 = \omega +1 = \omega(G')$$
e terminamos.
Então, vamos assumir que $\omega (G') = \omega$. Então $x$ não está em $K^{\omega} \subseteq G$: junto com $x'$, isso produziria um $K^{\omega +1}$ em $G'$. Vamos colorir $G$ com $\omega$ cores. Como todo $K^{\omega} \subseteq G$ atende à classe de cor $X$ de $x$, mas não ao próprio $x$, o grafo $H := G-(X \setminus \{x\})$ tem número de clique $\omega (H) < \omega$.
Uma vez que $G$ é perfeito, podemos estão colorir $H$ com $\omega -1$ cores. Agora $X$ é independente, então o conjunto $(X \setminus \{x\}) \cup \{x'\} = V(G'-H)$ também é independente. Podemos, portanto, estender nossa $(\omega -1)$-coloração de $H$ para uma $\omega$-coloração de $G'$, mostrando que $\chi (G') \leq \omega = \omega (G')$ é desejado.
Demonstração do Teorema de Lovász:
Aplicando indução em $|G|$, mostramos que o complemento $\overline{G}$ de qualquer grafo perfeito $G = (V,E)$ é novamente perfeito. Para $|G| = 1$ isso é trivial, então seja $|G| \geq 2$ para a etapa de indução. Seja $\mathcal{K}$ o conjunto de todos os conjuntos de vértices de subgrafos completos de $G$. Coloque $\alpha (G) =: \alpha$ e seja $\mathcal{A}$ o conjunto de todos os conjuntos $A$ de vértices independentes em $G$ com $|A| = \alpha$.
Todo subgrafo induzido próprio de $\overline{G}$ é o complemento de um subgrafo induzido próprio de $G$ e, portanto, é perfeito por indução. Para a perfeição de $\overline{G}$ basta provar $\chi (\overline{G}) \leq \omega (\overline{G}) (= \alpha)$. Para isso, encontraremos um conjunto $K \in \mathcal{K}$ tal que $K \cap A \neq \emptyset$ para todo $A \in \mathcal{A}$; então
$$\omega (\overline{G} -K) = \alpha (G -K) < \alpha = \omega (\overline{G}),$$
então pela hipótese de indução
$$\chi (\overline{G}) \leq \chi (\overline{G} -K)+1 = \omega (\overline{G} - K) +1 \leq \omega (\overline{G})$$
conforme desejado.
Suponha que não exista tal $K$; assim, para todo $K \in \mathcal{K}$ existe um conjunto $A_{K} \in \mathcal{A}$ com $K \cap A_{K} = \emptyset$. Substituamos em $G$ todo vértice $x$ por um grafo completo $G_{x}$ de ordem
$$k(x) := |\{ K \in \mathcal{K} \mid x \in A_{K} \}|,$$
unindo todos os vértices de $G_x$ a todos os vértices de $G_y$ sempre que $x$ e $y$ forem adjacentes em $G$ . O grafo $G'$ assim obtido tem um conjunto de vértices $\bigcup_{x \in V} V(G_x)$, e dois vértices $v \in G_x$ e $w \in G_y$ são adjacentes em $G'$ se, e somente se, $x = y$ ou $xy \in E$. Além disso, $G'$ pode ser obtido por expansão repetida de vértices do grafo $G [\{x \in V \mid k(x) > 0\}]$. Sendo um subgrafo induzido de $G$ , este último grafo é perfeito por suposição, então $G'$ é perfeito pelo Lema acima. Em particular,
$$\chi (G') \leq \omega (G'). \qquad (1)$$
Para obter uma contradição com $(1)$, agora calculamos alternadamente os valores reais de $\omega (G')$ e $\chi (G')$. Pela construção de $G'$, todo subgrafo completo maximal de $G'$ tem a forma $G'[ \bigcup _{x \in X} G_x]$ para algum $X \in \mathcal{K}$. Portanto, existe um conjunto $X \in \mathcal{K}$ tal que
$$\omega (G') = \sum_{x \in X} k(x) = |\{(x,K) : x \in X, K \in \mathcal{K}, x \in A_K\}|$$
$$\Downarrow$$
$$\omega (G') = \sum_{K \in \mathcal{K}} |X \cap A_K|$$
$$\Downarrow$$
$$\omega (G') \leq |\mathcal{K}|-1; \qquad (2)$$
a última desigualdade decorre do fato de que $|X \cap A_K| \leq 1$ para todo $K$ (já que $A_K$ é independente, mas $G[X]$ é completo) e $|X \cap A_X| = 0$ (pela escolha de $A_X$). Por outro lado,
$$|G'| = \sum_{x \in V} k(x) = |\{(x,K) : x \in V, K \in \mathcal{K},x \in A_K\}|$$
$$\Downarrow$$
$$|G'| = \sum_{K \in \mathcal{K}} |A_K| = |\mathcal{K}| * \alpha .$$
Como $\alpha (G') \leq \alpha$ pela construção de $G'$, isso implica
$$\chi (G') \geq \frac{|G'|}{\alpha(G')} \geq \frac{|G'|}{\alpha} = |\mathcal{K}|. \qquad (3)$$
Juntando $(2)$ e $(3)$, obtemos
$$\chi (G') \geq |\mathcal{K}| > |\mathcal{K}|-1 \geq \omega (G'),$$
uma contradição de $(1)$.
À primeira vista, a prova do Teorema de Lovász parece mágico: começa com um lema não motivado sobre a expansão de um vértice, desloca o problema para um estranho grafo $G'$ obtido dessa maneira, faz uma dupla contagem, e termina. Olhando para trás, no entanto, podemos entender um pouco melhor.
A prova é completamente natural até o ponto em que supomos que para todo $K \in \mathcal{K}$ existe um $A_K \in \mathcal{A}$ tal que $K \cap A_K = \emptyset$. Para mostrar que isso contradiz nossa suposição de que $G$ é perfeito, gostaríamos de mostrar a seguir que seu subgrafo $\tilde{G}$ induzido por todos os $A_K$ tem um número cromático muito grande, maior que seu número clique. E, como sempre quando tentamos limitar o número cormático por baixo, nossa única esperança é limitar $|\tilde{G}| / \alpha$, ou seja, mostrar que este é maior que $\omega (\tilde{G})$.
Mas é provável que o limite de $|\tilde{G}| / \alpha$ reflita o verdadeiro valor de $\chi (\tilde{G})$? Em um caso especial é: se os conjuntos $A_K$ são disjuntos, temos $|\tilde{G}| = |\mathcal{K}| * \alpha$ e $\chi (\tilde{G}) = |\mathcal{K}|$, com $A_K$ como classes de cores. Como todo subgrafo completo de $\tilde{G}$ encontra cada $A_{K'}$ no máximo uma vez e perde seu próprio $A_K$, então temos $\omega (\tilde{G}) < |\mathcal{K}| = \chi (\tilde{G})$ com a contradição desejada.
É claro que os conjuntos $A_K$ em geral não serão disjuntos. Mas podemos fazer isso: substituindo cada vértice $x$ por $k(x)$ vértices, onde $k(x)$ é o número de conjuntos $A_K$ em que ele vive. Esta é a ideia por trás de $G'$. O que resta é dotar $G'$ com o conjunto certo de arestas para torná-lo perfeito (supondo que $G$ seja perfeito), o que leva diretamente à definição de expansão de vértice e ao Lema.
Uma vez que a seguinte caracterização de perfeição é simétrica em $G$ e $\overline{G}$, ela implica claramente no Teorema de Lovász. Como nossa prova do Teorema de Lovász abaixo será novamente a partir dos primeiros princípios, obtemos assim uma segunda prova independente do Teorema de Lovász acima.
Teorema (Lovász 1972)
Um grafo $G$ é perfeito se, e somente se, $$|H| \leq \alpha (H) * \omega (H) \qquad (*)$$ para todo subgrafo induzido $H \subseteq G$.
Demonstração:
Vamos escrever $V(G) =: \{v_1, \dots, v_n\}$ e colocar $\alpha := \alpha (G)$ e $\omega := \omega (G)$. A necessidade de $(*)$ é imediata: se $G$ é perfeito, então todo subgrafo induzido $H$ de $G$ pode ser particionado em no máximo $\omega (H)$ classes de cores, cada uma contendo no máximo $\alpha(H)$ vértices, e $(*)$ segue.
Para provar a suficiência, aplicamos indução em $n = |G|$. Assuma que todo subgrafo induzido $H$ de $G$ satisfaz $(*)$ e suponha que $G$ não seja perfeito. Pela hipótese de indução , todo subgrafo induzido próprio de 4G$ é perfeito. Portanto, todo conjunto independente não vazio $U \subseteq V(G)$ satisfaz
$$\chi (G-U) = \omega (G-U) = \omega. \qquad (1)$$
De fato, enquanto a primeira igualdade é imediata da perfeição de $G-U$, a segunda é fácil: $'\leq '$ é óbvio , enquanto $\chi (G-U) < \omega$ implicaria $\chi (G) \leq \omega$, então $G$ seria perfeito ao contrário de nossa suposição .
Vamos aplicar $(1)$ a um conjutno unitário $U = \{u\}$ e considerar uma $\omega$-coloração de $G-u$. Seja $K$ o conjunto de vértices de qualquer $K^{\omega}$ em $G$. Claramente,
se $u \notin K$ então $K$ encontra todas as classes de cores de $G-u$; $\qquad (2)$
se $u \in K$, então $K$ atende a todas, exceto exatamente uma classe de cor de $G-u$. $\qquad (3)$
Seja $A_0 = \{u_1, \dots, u_{\alpha} \}$ um conjunto independente em $G$ de tamanho $\alpha$. Seja $A_1, \dots, A_{\omega}$ as classes de cores de uma $\omega$-coloração de $G-u_1$, sejam $A_{\omega +1}, \dots, A_{2 \omega}$ as classes de cores de uma $\omega$-coloração de $G-u_2$, e assim por diante; juntos, isso nos dá $\alpha \omega +1$ conjuntos independentes $A_0,A_1, \dots, A_{\alpha \omega}$ em $G$. Para cada $i=0,\dots, \alpha \omega$, existe por $(1)$ um $K^{\omega} \subseteq G-A_i$; denotamos seu conjunto de vértice definido por $K_i$.
Observe que se $K$ é o conjunto de vértices de qualquer $K^{\omega}$ em $G$, então
$$K \cap A_i = \emptyset, \qquad (4)$$
para exatamente um $i \in \{0,\dots, \alpha \omega\}$. De fato, se $K \cap A_0 = \emptyset$ então $K \cap A_i \neq \emptyset$ para todo $i \neq 0$, por definição de $A_i$ e $(2)$. Similarmente se $K \cap A_0 \neq \emptyset$, então $|K \cap A_0| = 1$, então $K \cap A_i = \emptyset$ para exatamente um $i \neq 0$: aplique $(3)$ ao único vértice $u \in K \cap A_0$ e $(2)$ a todos os outros vértices $u \in A_0$.
Seja $J$ a matriz real $(\alpha \omega +1) \times (\alpha \omega +1)$ com zero entradas na diagonal principal e todas as outras entradas $1$. Seja $A = (a_{ij})$ a matriz real $(\alpha \omega +1) \times n$ cujas linhas são os vetores de incidência dos conjuntos $A_i$ com $V(G)$: onde $a_{ij} = 1$, se $v_j \in A_i$, e $a_{ij} = 0$ caso contrário. Da mesma forma, seja $B$ denotando a matriz real $n \times (\alpha \omega +1)$ cujas colunas são os vetores de incidência dos conjuntos $K_j$ com $V(G)$. Agora, enquanto $|A_i \cap K_i| = 0$ para todo $i$ pela escolha de $K_i$, temos $A_i \cap K_j \neq \emptyset$ e, portanto, $A_i \cap K_j = 1$ sempre que $i \neq j$, por $(4)$. Assim,
$$AB = J.$$
Como $J$ não é singular, isso implica que $A$ tem classificação $\alpha \omega +1$. Em particular, $n \geq \alpha \omega +1$, que contradiz $(*)$ para $H := G$.
Pelo teorema, não podemos forçar um subgrafo $K^r$ , mesmo para $r = 3$, tornando o número cromático de um grafo suficientemente grande. No entanto, isso pode ser possível para grafos com certas propriedades especificadas, que podem, por sua vez, dar alguma importância a essas propriedades que, de outra forma, não teriam. Por exemplo, os grafos sem buraco ou antiburaco ímpar parecem uma classe ímpar para estudar. Mas o fato de que, pelo teorema do grafo perfeito forte, grafos de número cromático $k$ nesta classe possuem $K^k$ subgrafos, torna-os interessantes: alto número cromático, para grafos desta classe, sempre terá uma razão local.
De forma um pouco mais geral, uma classe $\mathcal{G}$ de grafos é chamada $\chi$-limitada se existe uma função $f: \mathbb{n} \to \mathbb{N}$ tal que $\chi (G) \leq f(r)$ para cada grafo $G \supsetneq K^r$ em $\mathcal{G}$. Em tais grafos, então, podemos forçar um subgrafo $K^r$ tornando $\chi$ maior que $f(r)$.
Teorema
$(i)$ O gráfico sem buracos ímpares é $\chi$-limitado com $f( r ) = 2^{2^{r+1}}$.
$(ii)$ Para cada inteiro $\ell$, o grafo sem buracos de comprimento $> \ell$ são $\chi$-limitados.
A questão óbvia que isso levanta é o que podemos dizer se ambas as condições forem combinadas: dado $\ell$, os grafos sem buraco ímpar de comprimento $> \ell$ ainda são $\chi$-limitados? Esta é certamente uma velha conjectura de Gýarfás, que motivou o Teorema logo acima.