Diferenças

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

--- grafos:perfectgraphs [2023/06/22 16:19] – edição externa 127.0.0.1
+++ grafos:perfectgraphs [2023/06/22 17:07] (atual) – edição externa 127.0.0.1
@@ Linha 226: / Linha 226: @@
 </WRAP>
-Seja X um conjunto independente em G de tamanho K. Seja K as classes de cores de uma coloração W de G, sejam K as classes de cores de uma coloração W de G, e assim por diante; juntos, isso nos dá K conjuntos independentes K em G. Para cada K, existe por 1 um K; denotamos seu vértice definido por K.
+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 em G, então K. De fato, se K então K para todo K, por definição de K e 2. Similarmente se K , então K , então K para exatamente um K; aplique 3 ao único vértice K e 2 a todos os outros vértices K.
+Observe que se $K$ é o conjunto de vértices de qualquer $K^{\omega}$ em $G$, então
-Seja J a matriz K real com zero entradas na diagonal principal e todas as outras entradas 1. Seja K a matriz K real cujas linhas são os vetores de incidência dos conjuntos K com V: onde K, e K caso contrário. Da mesma forma, seja B denotando a matriz K real cujas colunas são os vetores de incidência dos conjuntos K com V. Agora, enquanto K para todo J pela escolha de K, temos K e, portanto, K sempre que K, por 4. Assim, B. Como J não é singular , isso implica que K tem classificação K. Em particular, K, que contradiz (*) para H.
+$$K \cap A_i = \emptyset, \qquad (4)$$
-</WRAP>
-----
-Pelo teorema 5.2.5, não podemos forçar um subgrafo K , mesmo para K, tornando o número cromático de um grafo suficientemente grande. No entanto, isso pode ser possível para gráficos 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 ímpar ou antiburaco parecem uma classe estranha para estudar. Mas o fato de que, pelo teorema do grafo perfeito forte, grafos de número cromático K nesta classe possuem K subgrafos, torna-os interessantes: alto número cromático, para grafos desta classe, sempre terá uma razão local.
+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$.
-De forma um pouco mais geral, uma classe G de grafos é chamada limitada por X se existe uma função F tal que X para cada grafo G em G. Em tais grafos, então, podemos forçar um subgrafo K tornando X maior que F.
+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,
-Teorem 5.5.7
+$$AB = J.$$
-(i) O gráfico sem buracos ímpares é limitado por X com F.
+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$.
+</WRAP>
+----
-(ii) Para cada inteiro K, o grafo sem furos de comprimento K são limitados por X.
+Pelo [[grafos:teoerdos#teorema_erdos|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)$.
+<WRAP round box 100%>
+=== 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.//
+</WRAP>
 ----
-a questão óbvia que isso levanta é o que podemos dizer se ambas as condições forem combinadas: dado K, os gráficos sem buraco ímpar de comprimento K ainda são X limitados? esta é certamente uma velha conjectura de Gýarfás, que motivou o Teorema 5.5.7.
+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.