| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:colarestas [2023/06/12 14:52] – edição externa 127.0.0.1 | grafos:colarestas [2023/06/21 20:59] (atual) – edição externa 127.0.0.1 |
|---|
| ===== Colorações de arestas ===== | ==== Colorações de arestas ==== |
| |
| De maneira similiar a uma [[.numerdecores | coloração de vértices]], entederemos por [[.defcolarestas | coloração de arestas]] de um grafo $G = (V,E)$ uma função $c: E \to \{1,2,\dots,n\}$ tal que $c(e) \neq c(f)$ se $e$ e $f$ forem arestas adjacentes, isto é, possuírem uma extremidade em comum. Em particular, essa é uma coloração dos vértices do [[.linegraph | grafo das arestas]] de $G$. Nesse sentido, o menor número $n$ para o qual existe uma coloração de arestas $c: E \to \{1,2,\dots,n\}$ para $G$ é dito ser o [[.defcolarestas | número cromático de arestas]] desse grafo, denotado por [[.defcolarestas | $\chi'(G)$]]. Como antes $\{1,2,\dots,n\}$ é designado como o conjunto de cores da coloração. | De maneira similiar a uma [[.numerdecores | coloração de vértices]], entederemos por [[.defcolarestas | coloração de arestas]] de um grafo $G = (V,E)$ uma função $c: E \to \{1,2,\dots,n\}$ tal que $c(e) \neq c(f)$ se $e$ e $f$ forem arestas adjacentes, isto é, possuírem uma extremidade em comum. Em particular, essa é uma coloração dos vértices do [[.linegraph | grafo das arestas]] de $G$. Nesse sentido, o menor número $n$ para o qual existe uma coloração de arestas $c: E \to \{1,2,\dots,n\}$ para $G$ é dito ser o [[.defcolarestas | número cromático de arestas]] desse grafo, denotado por [[.defcolarestas | $\chi'(G)$]]. Como antes $\{1,2,\dots,n\}$ é designado como o conjunto de cores da coloração. |
| ---- | ---- |
| |
| O teorema de Vizing divide os grafos finitos em duas classes de acordo com seu índice cromático; grafos que satisfazem $\chi '=\Delta$ são chamados (imaginativamente) de //classe $\mathcal{1}$//, aqueles com X são de classe 2. Não há um bom teorema de caracterização que nos permita diferenciar essas classes, porque nenhum 'certificado' facilmente verificável é conhecido para um grafo como classe 2. | O teorema de Vizing divide os grafos finitos em duas classes de acordo com seu índice cromático; grafos que satisfazem $\chi '=\Delta$ são chamados (imaginativamente) de //classe// $1$, aqueles com $\chi ' = \Delta + 1$ são de //classe// $2$. Não há um bom teorema de caracterização que nos permita diferenciar essas classes, porque nenhum 'certificado' facilmente verificável é conhecido para um grafo como //classe// $2$. |
| |
| Gráficos regulares de grande ordem par e grande grau são classe 1: | Grafos regulares de grande ordem par e grande grau são classe $1$: |
| |
| | <WRAP round box 100%> |
| | === Teorema (Csaba, Kuhn, Lo, Osthus, Treglown) === |
| | //Existe um $n_0 \in \mathbb{N}$ tal que, para todo $n \geq n_0$ e $d \geq n/2$, todo grafo $d$-regular $G$ de ordem $n$ satisfaz $\chi '(G) = \Delta (G)$.// |
| | </WRAP> |
| |
| Existe um N tal que, para todo N e D, todo D-grafo regular G de ordem N satisfaz X. | ---- |
| | |
| | <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. 127-129. Acesso em 21/06/2023. |
| | |
| | </WRAP> |