| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:teoerdos [2023/06/12 13:31] – edição externa 127.0.0.1 | grafos:teoerdos [2023/06/12 14:15] (atual) – edição externa 127.0.0.1 |
|---|
| ==== Teorema de Erdós ==== | ==== 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$. | 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. | 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 $\chi _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 $\chi _k$, assim como no teorema da planaridade de Kurotowski com minors ou minors topológicos. Portanto, conter qualquer gráfico de $\chi _k$ é um certificado para $\chi \geq k$, e esses certificados juntos 'explicam' esse fenômeno no sentido discutido. | 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 \chi _k$ está de fato em $\chi_k$, ou apenas que $\chi (X) \geq k$? Voltaremos a esta questão em um momento. | 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 X é que K. Mas essa condição não é necessária: como o Teorema 5.2.5 mostrará, os grafos K-cromáticos nem precisam conter um triângulo. Portanto, embora K certamente esteja em X, não é seu único elemento. Reciprocamente, o Lema 5.2.3 implica que todos os graohs em X têm grau mínimo pelo menos K; mas nem todos os grafos de grau mínimo K estão em X, pois eles não precisam satisfazer X. | 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 Erdos implica que X não pode ser finito. De fato, isso implica que para nenhum K existe um conjunto finito X de subgrafos X com X tal que todo grafo K-cromático possui um subgrafo em X: | 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}$: |
| |
| teorema 5.2.5 | <WRAP round box 100%> |
| | === Teorema (Erdós) === |
| Para todo inteiro K existe um grafo G com perímetro G e número cromático X. | //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 5.2.5 foi provado pela primeira vez de forma não construtiva usando grafos aleatórios, e daremos essa prova no Capítulo 11.2. Construir gráficos de grande número cromático e circunferência diretamente não é fácil. | 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 Erdo é 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. | 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, vamos definir a classe de grafos K-construtíveis recursivamente da seguinte forma: | 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; | $(i)$ $K^k$ é $k$-contrutível; |
| {{ :grafos:graphs5236.png?500 |}} | {{ :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 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 e Y não têm ambos a mesma cor que X, então esta coloração induz uma coloração de G ou G e, portanto, usa pelo menos K cores. | 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: | É notável, porém, que o inverso também seja válido: |
| |
| Teorema 5.2.6 | <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> |
| |
| Seja G um grafo e K. Então X se e somente se G tiver um subgrafo K-construtível. | <WRAP round box 100%> |
| | //**Demonstração:**// |
| |
| Dem.: | 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$. |
| |
| Seja G um grafo com X; mostramos que H tem um subgrafo K-construtível. Suponha que não; então K. 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 X implicaria R, e G conteria o grafo K-construtível 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)$. |
| |
| Como G não é um grafo multipartido completo, a não-adjacência não é uma relação equivalente em V. Portanto, existem vértices X tais que X, mas Y. Como G é aresta máxima sem um subgrafo K-construtível, cada aresta X está em algum Subgrafo K-construtível H de G. | 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 |
| |
| Seja H uma cópia isomórfica de H que contém X e H, mas é disjunta de G, junto com um isomorfismo V de H para H que faz H ponto a ponto. Então H, então H é $k$-contrutível por $(iii)$. Um vértice de cada vez, identifiquemos em H cada vértice V com seu parceiro V; como V 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; este é o subgrafo K-construtível desejado de G. | $$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 X 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 K realmente precisa de pelo menos K cores. Consulte a nota para obter detalhes. | 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> |