grafos:colarestas [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
==== 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.

Uma primeira observação que se estabelece frente essa definição é que $\chi'(G) \geq$ [[.graumaximo | $\Delta(G)$]] para todo grafo $G = (V,E)$. Afinal, se $v$ é um vértice de grau máximo em $G$, todas as arestas que nele incidem são duas a duas adjacentes, pois possuem $v$ como extremidade em comum. Elas precisam, portanto, receber cores diferentes em qualquer coloração de arestas. Ainda assim, essa quantidade é suficiente em certas classes de grafos, como os [[.defbipartite | bipartidos]]:

<WRAP round box 100%>
=== Proposição (König) ===
//Se $G = (V,E)$ é um grafo bipartido, então $\chi'(G) = \Delta(G)$.//
</WRAP>

<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$.

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.

<WRAP round box 100%>
=== Teorema (Vizing) === 
//Para qualquer grafo $G = (V,E)$, tem-se//

$$\Delta(G) \leq \chi'(G) \leq \Delta(G)+1.$$
</WRAP>

<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:
  * Essas arestas são duas a duas distintas, ou seja, $y_i \neq y_j$ se $1\leq i,j \leq k$ são diferentes. Em particular, $k \leq \Delta(G)$.
  * $y = y_1$.
  * Para cada $2 \leq i \leq k$, a cor recebida pela aresta $xy_i$ é $i$.
  * Para cada $2 \leq i \leq k$, a cor recebida pela aresta $i$ está ausente em $y_{i-1}$.   

Com essa definição, fixe $(xy_1,xy_2,\dots,xy_k)$ um leque de forma que $k$ atinja seu valor máximo. Argumentaremos agora que, se existe uma cor ausente em $x$ e em $y_k$, a prova pode ser finalizada. Isso porque, como principal objetivo da definição de leque, podemos colorir a aresta $xy_j$ com a cor $j+1$ se $j < k$ e colorir a aresta $xy_k$ com a cor ausente tanto em $x$ quanto em $y_i$. Em particular, como $y = y_1$, a aresta $xy$ encontra-se agora colorida.

Então, resta-nos considerar a situação em que toda cor ausente em $y_k$ está presente em $x$. Pela maximalidade do leque, então, as cores ausentes em $y_k$ pertencem ao conjunto $\{2,3,\dots,k-1\}$. Seja $i$ uma dessas cores ausentes em $y_k$ e, a menos de troca de nomes de cores, suponha que a cor $1$ está ausente em $x$. Defina $H$ como o subgrafo de $G\setminus xy$ cujas arestas têm cores $1$ ou $i$. Novamente, como arestas de cores iguais não podem ter uma extremidade em comum, nenhum vértice de $H$ tem grau maior ou igual a $3$. Assim, as componentes conexas desse subgrafo são [[.auxiliarbrooks | ciclos ou caminhos]]. Mais precisamente, as componentes que contém $x$, $y_k$ e $y_{i-1}$ são caminhos, pois nesses vértices a cor $1$ é ausente ou a cor $i$ é ausente. Nessa situação, um dos seguintes casos se verifica:
  * 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.

<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>