grafos:teoerdos [WikiMat]

==== Teorema de Erdós e o Teorema de Hajós ====

Até agora vimos algumas condições necessárias para alta cromaticidade, na forma de limites superiores em $\chi$. Se $\chi (G) \geq k$, por exemplo, então também $\Delta geq k$ (a menos que $G$ seja completo ou um ciclo ímpar), e $G$ tem um subgrafo de grau mínimo em menos $k-1$. Porém, essas condições estão longe de ser suficientes: se $G=K_{n,n}$, digamos, elas valem para todo $k \leq n$, exceto $\chi (G) =2$.

Seria bom também ter algumas condições suficientes para $\chi \geq k$. Se elas forem fáceis de verificar, elas podem fornecer certificados úteis de o por que não conseguimos colorir um determinado grafo com poucas cores. Se eles pudessem ser mostrados como necessários também, eles 'explicariam' por que certos grafos são altamente cromáticos, assim como a condição de casamento no teorema de Hall 'explicaria' por que certos emparelhamentos em grafos bipartidos falham: sua violação claramente impede que um grafo tenha o emparelhamento desejado e é violada toda vez que tal emparelhamento não existe.

Por exemplo, podemos tentar determinar a classe $\mathcal{X} _k$ de grafos $\subseteq$-mínimos que não podem ser coloridos com menos de $k$ cores. Como é fácil verificar (cf. **Lema 12.6.1**), um dado grafo $G$ satisfaz $\chi (G) \geq k$ se, e somente se, possui um subgrafo em $\mathcal{X}_k$, assim como no teorema da planaridade de Kurotowski com minors ou minors topológicos. Portanto, conter qualquer gráfico de $\mathcal{X} _k$ é um certificado para $\chi \geq k$, e esses certificados juntos 'explicam' esse fenômeno no sentido discutido.

Mas esses certificados serão fáceis de encontrar em um gráfico $k$-cromático arbitrário ou pelo menos fáceis de verificar? Ou seja, será fácil verificar se um determinado grafo $X \in \mathcal{X} _k$ está de fato em $\mathcal{X} _k$, ou apenas que $\chi (X) \geq k$? Voltaremos a esta questão em um momento.

Uma condição óbvia e suficiente para $\chi (G) \geq k$ é que $K^k \subseteq G$. Mas essa condição não é necessária: como o Teorema de Erdós mostrará, os grafos $k$-cromáticos nem precisam conter um triângulo. Portanto, embora $K^k$ certamente esteja em $\mathcal{X} _k$, não é seu único elemento. Reciprocamente, o [[.lemakcolor | Lema]] implica que todos os grafos em $\mathcal{X} _k$ têm grau mínimo pelo menos $k-1$; mas nem todos os grafos de grau mínimo $k-1$ estão em $\mathcal{X}_k$, pois eles não precisam satisfazer $\chi \geq k$.

O seguinte teorema de Erdós implica que $\mathcal{X}_k$ não pode ser finito. De fato, isso implica que para nenhum $k$ existe um conjunto finito $\mathcal{X}$ de grafos $X$ com $\chi (X) \geq 3$ tal que todo grafo $k$-cromático possui um subgrafo em $\mathcal{X}$:

<WRAP round box 100%>
=== Teorema (Erdós) ===
//Para todo inteiro $K$ existe um grafo $G$ com circunferência $g(G) >k$ e número cromático $\chi (G) > k$.//
</WRAP>

----

O teorema acima foi provado pela primeira vez de forma não construtiva usando grafos aleatórios, e reproduziremos essa prova mais a frente. Construir gráficos de grande número cromático e circunferência diretamente não é fácil.

A mensagem do teorema de Erdós é que, talvez ao contrário do que esperávamos, um grande número cromático pode ocorrer como um fenômeno puramente global: localmente, em torno de cada vértice, um grafo de grande circunferência se parece com uma árvore e, em particular, é $2$- colorido lá. Mas o que exatamente pode causar alta cromaticidade como um fenômeno glocal permanece um mistério.

No entanto, existe um procedimento simples, embora nem sempre curto, para construir todos os grafos de número cromático pelo menos $k$. Para cada $k \in \mathbb{N}$, vamos definir a classe de grafos $k$-construtíveis recursivamente da seguinte forma:

$(i)$ $K^k$ é $k$-contrutível;

$(ii)$ Se $G$ é $k$-construtível e dois vértices $x,y$ de $G$ não são adjacentes, então $(G+xy)/xy$ também é $k$-construtível.

$(iii)$ Se $G_1,G_2$ são $k$-construtíveis e existem vértices $x,y_1,y_2$ tais que $G_1 \cap G_2 = \{x\}$ e $xy_1 \in E(G_1)$ e $xy_2 \in E(G_2)$, então $(G_1 \cap G_2)-xy_1-xy_2 +y_1y_2$ também é $k$-construtível.

{{ :grafos:graphs5236.png?500 |}}

Pode-se facilmente verificar indutivamente que todos os grafos $k$-construtíveis e, portanto, seus supergrafos, são pelo menos $k$-cromáticos. Por exemplo, qualquer coloração do grafo $(G+xy)/xy$ em $(ii)$ induz uma coloração de $G$ e, portanto, por suposição indutiva, usa pelo menos $k$ cores. Da mesma forma, em qualquer coloração do grafo construído em $(iii)$, os vértices $y_1$ e $y_2$ não têm ambos a mesma cor que $x$, então esta coloração induz uma coloração de $G_1$ ou $G_2$ e, portanto, usa pelo menos $k$ cores.

É notável, porém, que o inverso também seja válido:

<WRAP round box 100%>
=== Teorema (Hajós) ====
//Seja $G$ um grafo e $k \in \mathbb{N}$. Então $\chi (G) \geq k$ se, e somente se, $G$ tiver um subgrafo $k$-construtível.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Seja $G$ um grafo com $\chi (G) \geq k$; mostramos que $G$ tem um subgrafo $k$-construtível. Suponha que não; então $k \geq 3$. Adicionando algumas arestas se necessário, vamos fazer $G$ aresta-maximal com a propriedade de que nenhum de seus subgrafos é $k$-construtível. Agora $G$ não é um grafo $r$-partido completo para qualquer $r$: então $\chi (G) \geq k$ implicaria $r \geq k$, e $G$ conteria o grafo $k$-construtível $K^k$.

Como $G$ não é um grafo multipartido completo, a não-adjacência não é uma relação equivalente em $V(G)$. Portanto, existem vértices $y_1,x,y_2$ tais que $y_1x,xy_2 \notin E(G)$, mas $y_1y_2 \in E(G)$. Como $G$ é aresta-máximal sem um subgrafo $k$-construtível, cada aresta $xy_i$ está em algum subgrafo $k$-construtível $H_i$ de $G+xy_i (i=1,2)$.

Seja $H_2'$ uma cópia isomórfica de $H_2$ que contém $x$ e $H_2-H_1$, mas é disjunta de $G$, junto com um isomorfismo $v \mapsto v'$ de $H_2$ para $H_2'$ que fixa $H_2 \cap H_2'$ ponto a ponto. Então $H_1 \cap H_2' = \{x\}$, então 

$$H := (H_1 \cup H_2')-xy_1-xy_2' +y_1y_2'$$

é $k$-contrutível por $(iii)$. Um vértice de cada vez, identifiquemos em $H$ cada vértice $v' \in H_2'-G$ com seu parceiro $v$; como $vv'$ nunca é uma aresta de $H$, cada uma dessas identificações equivale a uma etapa de construção do tipo $(ii)$. Eventualmente, obtemos o grafo

$$(H_1 \cup H_2) -xy_1-xy_2+y_1y_2 \subseteq G;$$ 

este é o subgrafo $k$-construtível desejado de $G$.
</WRAP>

----

O teorema de Hajós resolve nosso problema do tipo Kuratowski para grafos altamente cromáticos, que era encontrar uma classe de grafos de número cromático pelo menos $k$ com a propriedade de que todo grafo tem subgrafo nessa classe? Formalmente, sim, embora com uma classe de caracterização infinita (a classe de grafos K-construtíveis) que contém $\mathcal{X}_k$ adequadamente. Ao contrário da caracterização de grafos planares de Kuratowski, no entanto, isso não torna, pelo menos não obviamente, o teorema de Hajó uma boa caracterização dos grafos do número cromático $<k$: como se pode mostrar, provando que um determinado grafo $k$-construtível é de fato $k$-construtível é tão difícil quanto provar que um gráfico de número cromático $\geq k$ realmente precisa de pelo menos $k$ cores. **Consulte a nota para obter detalhes.***

----

<WRAP round info 100%>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 125-127. Acesso em 10/06/2023.

</WRAP>