Proposição (König)

Se $G = (V,E)$ é um grafo bipartido, então $\chi'(G) = \Delta(G)$.

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

$\square$

Teorema (Vizing)

Para qualquer grafo $G = (V,E)$, tem-se

$$\Delta(G) \leq \chi'(G) \leq \Delta(G)+1.$$

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

$\square$

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