| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:perfectgraphs [2023/06/22 16:31] – edição externa 127.0.0.1 | grafos:perfectgraphs [2023/06/22 17:07] (atual) – edição externa 127.0.0.1 |
|---|
| 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$. | 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 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. | 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$. |
| </WRAP> | </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. | 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 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. | 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)$. |
| |
| Teorem 5.5.7 | <WRAP round box 100%> |
| | === Teorema === |
| (i) O gráfico sem buracos ímpares é limitado por X com F. | $(i)$ //O gráfico sem buracos ímpares é $\chi$-limitado com $f( r ) = 2^{2^{r+1}}$.// |
| | |
| (ii) Para cada inteiro K, o grafo sem furos de comprimento K são limitados por X. | |
| |
| | $(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. |