Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:teoerdos [2023/06/12 13:47] – piva
+++ grafos:teoerdos [2023/06/12 14:15] (atual) – edição externa 127.0.0.1
@@ Linha 34: / Linha 34: @@
 {{ :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:
-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>