Diferenças

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

--- grafos:colarestas [2023/06/12 14:47] – piva
+++ grafos:colarestas [2023/06/21 20:59] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 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.
@@ Linha 55: / Linha 55: @@
 ----
+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$.
+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>
+----
+<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>