grafos:colarestas

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:colarestas [2023/06/12 14:55] – pivagrafos: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. 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 62: Linha 62:
 === Teorema (Csaba, Kuhn, Lo, Osthus, Treglown) === === 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)$.// //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> </WRAP>
  • grafos/colarestas.1686592510.txt.gz
  • Última modificação: 2023/06/12 14:55
  • por piva