| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:perfectgraphs [2023/06/22 16:38] – edição externa 127.0.0.1 | grafos:perfectgraphs [2023/06/22 17:07] (atual) – edição externa 127.0.0.1 |
|---|
| $$AB = J.$$ | $$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 $(*)4 para $H := G$. | 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. |