| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:colarestas [2023/06/12 14:44] – 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. |
| </WRAP> | </WRAP> |
| |
| __//Demonstração://__ Pela observação acima, basta mostrar que $\chi'(G) \leq \Delta(G)$ se $G$ é um grafo bipartido. Provaremos isso por indução na quantidade de arestas de $G$, observando que o enunciado trivialmente se verifica se $|E| = 0$. Se $|E|>0$, fixe então $xy\in E$ qualquer. Por hipótese indutiva, é possível colorir as arestas do grafo (também bipartido) $H = G\setminus xy$ com $\Delta(H)$ cores. Em particular, como $\Delta(H)\leq \Delta(G)$, é possível utilizar $\Delta(G)$ cores para colorir as arestas de $H$. Observamos ainda que, em $H$, os vértices $x$ e $y$ não possuem grau $\Delta(G)$, pois um é vizinho do outro em $G$. Assim, ao fixarmos uma coloração para as arestas de $H$ com cores em $\{1,2,\dots, \Delta(G)\}$, existem $1 \leq i,j \leq \Delta(G)$ cores tais que: nenhuma aresta colorida com $i$ incide em $x$ e nenhuma aresta colorida com $j$ incide em $y$. Ora, se podemos tomar $i=j$ com essas propriedades, basta estender essa coloração para o grafo $G$ colorindo a aresta $xy$ com a cor $i =j$. | <WRAP round box 100%> |
| | **//Demonstração://** |
| | |
| | Pela observação acima, basta mostrar que $\chi'(G) \leq \Delta(G)$ se $G$ é um grafo bipartido. Provaremos isso por indução na quantidade de arestas de $G$, observando que o enunciado trivialmente se verifica se $|E| = 0$. Se $|E|>0$, fixe então $xy\in E$ qualquer. Por hipótese indutiva, é possível colorir as arestas do grafo (também bipartido) $H = G\setminus xy$ com $\Delta(H)$ cores. Em particular, como $\Delta(H)\leq \Delta(G)$, é possível utilizar $\Delta(G)$ cores para colorir as arestas de $H$. Observamos ainda que, em $H$, os vértices $x$ e $y$ não possuem grau $\Delta(G)$, pois um é vizinho do outro em $G$. Assim, ao fixarmos uma coloração para as arestas de $H$ com cores em $\{1,2,\dots, \Delta(G)\}$, existem $1 \leq i,j \leq \Delta(G)$ cores tais que: nenhuma aresta colorida com $i$ incide em $x$ e nenhuma aresta colorida com $j$ incide em $y$. Ora, se podemos tomar $i=j$ com essas propriedades, basta estender essa coloração para o grafo $G$ colorindo a aresta $xy$ com a cor $i =j$. |
| |
| Suponha então que $i \neq j$ e, além disso, que existem uma aresta $e$ de cor $j$ com ponta em $x$ e uma aresta $f$ de cor $i$ incidente em $y$. Nesse caso, considere um [[.walk | passeio]] $W$ maximal em $H$ contendo $e$ e cujas demais arestas têm cores $i$ ou $j$. Em particular, como arestas adjacentes estão coloridas com cores distintas, nesse passeio não deve haver um vértice de grau maior ou igual a $3$. Logo, como nenhuma aresta de cor $i$ incide em $x$, [[.auxiliarbrooks | o passeio $H$ é na verdade um caminho]]. Uma de suas extremidades trivialmente é o vértice $x$. A outra, contudo, não pode ser $y$: se fosse, a aresta de $W$ que incide em $y$ deve ser a $f$, pois nenhuma aresta de cor $j$ incide nesse vértice. Portanto, como $W$ é um caminho formado por arestas de cores $i$ e $j$ alternadamente, obtemos que $E(W)\cup \{xy\} $ é um conjunto de arestas que define um ciclo ímpar, [[.defbipartite | contradizendo]] o fato de $G$ ser um grafo bipartido. Destacamos também que $y$ não pode ser um vértice de grau $2$ em $W$, pois, nesse caso, alguma aresta de cor $j$ (do próprio caminho $W$) teria ponta em $y$. | Suponha então que $i \neq j$ e, além disso, que existem uma aresta $e$ de cor $j$ com ponta em $x$ e uma aresta $f$ de cor $i$ incidente em $y$. Nesse caso, considere um [[.walk | passeio]] $W$ maximal em $H$ contendo $e$ e cujas demais arestas têm cores $i$ ou $j$. Em particular, como arestas adjacentes estão coloridas com cores distintas, nesse passeio não deve haver um vértice de grau maior ou igual a $3$. Logo, como nenhuma aresta de cor $i$ incide em $x$, [[.auxiliarbrooks | o passeio $H$ é na verdade um caminho]]. Uma de suas extremidades trivialmente é o vértice $x$. A outra, contudo, não pode ser $y$: se fosse, a aresta de $W$ que incide em $y$ deve ser a $f$, pois nenhuma aresta de cor $j$ incide nesse vértice. Portanto, como $W$ é um caminho formado por arestas de cores $i$ e $j$ alternadamente, obtemos que $E(W)\cup \{xy\} $ é um conjunto de arestas que define um ciclo ímpar, [[.defbipartite | contradizendo]] o fato de $G$ ser um grafo bipartido. Destacamos também que $y$ não pode ser um vértice de grau $2$ em $W$, pois, nesse caso, alguma aresta de cor $j$ (do próprio caminho $W$) teria ponta em $y$. |
| |
| Então, observamos que é possível trocar em $W$ as cores $i$ e $j$ sem que arestas adjacentes recebam cores iguais, por conta da maximalidade de $W$ como passeio com arestas de cores $i$ ou $j$. Isso descreve uma coloração de arestas em que nenhuma aresta de cor $j$ incide em $x$. Afinal, a aresta $e$, a única que possuía essa cor e tinha esse vértice como extremidade, tem agora cor $i$. Da mesma forma, nenhuma aresta de cor $j$ incide em $y$, pois trocamos apenas cores de arestas do caminho $W$. Essa nova coloração, portanto, pode ser estendida para todo o grafo $G$ ao colorirmos a aresta $xy$ com a cor $j$. <wrap right>$\square$</wrap> | Então, observamos que é possível trocar em $W$ as cores $i$ e $j$ sem que arestas adjacentes recebam cores iguais, por conta da maximalidade de $W$ como passeio com arestas de cores $i$ ou $j$. Isso descreve uma coloração de arestas em que nenhuma aresta de cor $j$ incide em $x$. Afinal, a aresta $e$, a única que possuía essa cor e tinha esse vértice como extremidade, tem agora cor $i$. Da mesma forma, nenhuma aresta de cor $j$ incide em $y$, pois trocamos apenas cores de arestas do caminho $W$. Essa nova coloração, portanto, pode ser estendida para todo o grafo $G$ ao colorirmos a aresta $xy$ com a cor $j$. |
| | |
| | <wrap right>$\square$</wrap> |
| | </WRAP> |
| | |
| | ---- |
| |
| Diferentemente da teoria de colorações de vértices, a teoria de coloração de arestas é capaz de determinar um excelente limitante superior para o número mínimo de cores a serem utilizadas. Com o resultado a seguir, tem-se que, para todo grafo $G$, a grandeza $\chi'(G)$ assume no máximo dois valores: $\Delta(G)$ ou $\Delta(G)+1$. Apesar disso, não existem caracterizações ou indícios claros de quando cada um desses valores é assumido. | Diferentemente da teoria de colorações de vértices, a teoria de coloração de arestas é capaz de determinar um excelente limitante superior para o número mínimo de cores a serem utilizadas. Com o resultado a seguir, tem-se que, para todo grafo $G$, a grandeza $\chi'(G)$ assume no máximo dois valores: $\Delta(G)$ ou $\Delta(G)+1$. Apesar disso, não existem caracterizações ou indícios claros de quando cada um desses valores é assumido. |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| **Teorema (** Vizing **):** //Para qualquer grafo $G = (V,E)$, tem-se $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$.// | === Teorema (Vizing) === |
| | //Para qualquer grafo $G = (V,E)$, tem-se// |
| | |
| | $$\Delta(G) \leq \chi'(G) \leq \Delta(G)+1.$$ |
| </WRAP> | </WRAP> |
| |
| __//Demonstração://__ A desigualdade $\Delta(G) \leq \chi'(G)$ foi estabelecida anteriormente. Por indução sobre a quantidade de arestas de $G$, então, mostraremos que $\chi'(G) \leq \Delta(G)+1$. O caso base desse processo indutivo, em que $|E| = 0$, é trivialmente verificado. Caso $G$ tenha uma aresta $xy \in E$, utilize a hipótese indutiva para fixar uma coloração das arestas de $G\setminus xy$ com cores em $\{1,2,\dots, \Delta(G)+1\}$. Observamos que isso é possível pois $\Delta(G\setminus xy) \leq \Delta(G)$. | <WRAP round box 100%> |
| | **//Demonstração://** |
| | |
| | A desigualdade $\Delta(G) \leq \chi'(G)$ foi estabelecida anteriormente. Por indução sobre a quantidade de arestas de $G$, então, mostraremos que $\chi'(G) \leq \Delta(G)+1$. O caso base desse processo indutivo, em que $|E| = 0$, é trivialmente verificado. Caso $G$ tenha uma aresta $xy \in E$, utilize a hipótese indutiva para fixar uma coloração das arestas de $G\setminus xy$ com cores em $\{1,2,\dots, \Delta(G)+1\}$. Observamos que isso é possível pois $\Delta(G\setminus xy) \leq \Delta(G)$. |
| |
| Para descrevermos uma coloração para o grafo $G$, faremos uso de certas notações auxiliares. Primeiro, diremos que uma cor $1 \leq i\leq \Delta(G)+1$ está //presente// em um vértice $v\in V$ se alguma aresta que incide nele está colorida com essa cor. Caso contrário, dizemos que essa cor está //ausente// nesse vértice. Como $\Delta(G)+1$ cores estão sendo utilizadas, em todo vértice há uma cor ausente. Assim, definimos um //leque// sobre o vértice $x$ (fixado como extremidade da aresta $xy$ removida) como uma ordenação $(xy_1,xy_2,\dots,xy_k)$ de arestas nele incidentes tal que: | Para descrevermos uma coloração para o grafo $G$, faremos uso de certas notações auxiliares. Primeiro, diremos que uma cor $1 \leq i\leq \Delta(G)+1$ está //presente// em um vértice $v\in V$ se alguma aresta que incide nele está colorida com essa cor. Caso contrário, dizemos que essa cor está //ausente// nesse vértice. Como $\Delta(G)+1$ cores estão sendo utilizadas, em todo vértice há uma cor ausente. Assim, definimos um //leque// sobre o vértice $x$ (fixado como extremidade da aresta $xy$ removida) como uma ordenação $(xy_1,xy_2,\dots,xy_k)$ de arestas nele incidentes tal que: |
| * Se $x$ e $y_{i-1}$ não pertencem a mesma componente conexa de $H$, faremos a troca das cores $1$ e $i$ na componente em que se encontra $y_{i-1}$, observando que isso determina de fato uma coloração de arestas. Nesse novo cenário, a cor $1$ está ausente no vértice $y_{i-1}$ (se é que já não estava ausente antes, inclusive), bem como continua ausente no vértice $x$. Agora, $(xy_1,xy_2,\dots,xy_{i-1})$ é um leque com respeito a essa nova coloração. Podemos então colorir $xy_{i-1}$ com a cor $1$ e $xy_j$ com a cor $j+1$ para todo $1 \leq j \leq i-2$. Em particular, a aresta $xy$ está colorida, finalizando o processo indutivo nesse caso. | * Se $x$ e $y_{i-1}$ não pertencem a mesma componente conexa de $H$, faremos a troca das cores $1$ e $i$ na componente em que se encontra $y_{i-1}$, observando que isso determina de fato uma coloração de arestas. Nesse novo cenário, a cor $1$ está ausente no vértice $y_{i-1}$ (se é que já não estava ausente antes, inclusive), bem como continua ausente no vértice $x$. Agora, $(xy_1,xy_2,\dots,xy_{i-1})$ é um leque com respeito a essa nova coloração. Podemos então colorir $xy_{i-1}$ com a cor $1$ e $xy_j$ com a cor $j+1$ para todo $1 \leq j \leq i-2$. Em particular, a aresta $xy$ está colorida, finalizando o processo indutivo nesse caso. |
| * Se $x$ e $y_{i-1}$ pertencem à mesma componente conexa de $H$, que é um caminho, esses vértices são suas extremidades. Assim, como a cor $i$ é ausente em $y_k$, o vértice $y_k$ está em uma componente conexa distinta da de $x$. Como antes, então, trocaremos as cores $1$ e $i$ nas arestas dessa componente. Isso define uma nova coloração de arestas em que a cor $1$ se torna ausente em $y_k$, embora $1$ continue ausente em $x$ e $i$ continue ausente em $y_{i-1}$ - visto que a coloração não foi mudada na componente de $H$ que contém esses vértices. Com respeito a essa nova coloração, a sequência $(xy_1,xy_2,\dots,xy_k)$ é também um leque, mas agora é possível colorir a aresta $xy_k$ com a cor $1$ e cada aresta $xy_j$ com a cor $j+1$, para todo $1 \leq j \leq k-2$. Em particular, a aresta $xy = xy_1$ está colorida, finalizando o processo indutivo nesse caso. | * Se $x$ e $y_{i-1}$ pertencem à mesma componente conexa de $H$, que é um caminho, esses vértices são suas extremidades. Assim, como a cor $i$ é ausente em $y_k$, o vértice $y_k$ está em uma componente conexa distinta da de $x$. Como antes, então, trocaremos as cores $1$ e $i$ nas arestas dessa componente. Isso define uma nova coloração de arestas em que a cor $1$ se torna ausente em $y_k$, embora $1$ continue ausente em $x$ e $i$ continue ausente em $y_{i-1}$ - visto que a coloração não foi mudada na componente de $H$ que contém esses vértices. Com respeito a essa nova coloração, a sequência $(xy_1,xy_2,\dots,xy_k)$ é também um leque, mas agora é possível colorir a aresta $xy_k$ com a cor $1$ e cada aresta $xy_j$ com a cor $j+1$, para todo $1 \leq j \leq k-2$. Em particular, a aresta $xy = xy_1$ está colorida, finalizando o processo indutivo nesse caso. |
| | |
| <wrap right>$\square$</wrap> | <wrap right>$\square$</wrap> |
| | </WRAP> |
| | |
| | ---- |
| |
| | 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> |