grafos:colouringintro [WikiMat]

Quantas cores precisamos para colorir os países de um mapa de forma que os países adjacentes tenham cores diferentes? Quantos dias devem ser agendados para as reuniões das comissões de um parlamento se todas as comissões pretendem se reunir por um dia e alguns membros do parlamento servem em várias comissões? Como podemos encontrar um horário escolar de duração total mínima, com base nas informações de quantas vezes cada professor deve lecionar em cada classe?

Uma coloração de vértice de um grafo $G=(V,E)$ é um mapa $\mathcal{c} : V \to S$ tal que $\mathcal{c}(v) \neq \mathcal{c}(w)$ sempre que $v$ e $w$ são adjacentes. Os elementos do conjunto $S$ são chamados de cores disponíveis. Tudo o que nos interessa sobre $S$ é o seu tamanho: tipicamente, estaremos pedindo o menor inteiro $k$ tal que $G$ tenha uma $k$-coloração , um vértice colorindo $\mathcal{c} : V \to \{1,\dots, k\}$. Este $k$ é o (vértice-)número cromático de $G$; é denotado por $\chi(G)$. Um grafo $G$ com $\chi(G)=k$ é chamado $k$-cromático; se $\chi(G) \leq k$, chamamos $G$ $k$-colorível.

Um vértice colorindo $V \to \{1,\dots,4\}$:

Observe que uma $k$-coloração nada mais é do que uma partição de vértices em $k$ conjuntos independentes, agora chamados de classes de cores; os grafos $2$-coloríveis não triviais, por exemplo, são precisamente os grafos bipartidos. Historicamente, a terminologia de coloração vem do problema de coloração de mapas mencionado acima, que leva ao problema de determinar o número cromático máximo de grafos planares. O problema de agendamento do comitê também pode ser formulado como um problema de coloração de vértices.

Uma coloração de aresta de $G$ é um mapa $\mathcal{c} : E \to S$ com $\mathcal{c}(e) \neq \mathcal{c}(f)$ para quaisquer arestas adjacentes $e,f$. O menor inteiro $k$ para o qual existe uma $k$-coloração-aresta k, ou seja, uma coloração de aresta $\mathcal{c}: E \to \{1,\dots,k\}$, é o número cromático de aresta, ou índice cromático, de $G$; é denotado por $\chi'(G)$. A terceira de nossas questões introdutórias pode ser modelada como um problema de coloração de arestas em um multigrafo bipartido.

Claramente, toda coloração de arestas de $G$ é uma coloração de vértice de seu grafo de linha $L(G)$, e vice-versa; em particular, $\chi'(G) = \chi(L(G))$. O problema de encontrar boas colorações de arestas pode, portanto, ser visto como uma restrição do problema mais geral de coloração de vértices a essa classe especial de grafos. Como veremos, essa relação entre os dois tipos de problema de coloração é refletida por uma diferença marcante em nosso conhecimento sobre suas soluções: embora existam apenas estimativas muito aproximadas para $\chi$, seu irmão $\chi'$ sempre assume um dos dois valores, $\Delta$ ou $\Delta +1$.

Se algum resultado na teoria dos grafos tem a pretensão de ser conhecido pelo mundo exterior, é o seguinte teorema das quatro cores, que implica que todo mapa pode ser colorido com no máximo quatro cores:

Teorema das Quatro Cores

Todo grafo planar é $4$-colorível.

Entretanto, por ora, provemos o seguinte enfraquecimento:

Teorema das Cinco Cores

Todo grafo planar é $5$-colorível.

Demonstração:

Seja $G$ um grafo plano com $n \geq 6$ vértices e $m$ arestas. Assumimos indutivamente que todo grafo plano com menos de $n$ vértices pode ser $5$-colorido. Pelo Corolário 4.2.10,

$$d(G) = 2m / n \leq 2(3n-6) / n <6;$$

seja $v \in G$ um vértice de grau no máximo $5$. Pela hipótese de indução, o grafo $H := G-v$ tem uma coloração de vértice $\mathcal{c} : V(H) \to \{1, \dots ,5\}$. Se $\mathcal{c}$ usa no máximo $4$ cores para os vizinhos de $v$, podemos estendê-lo para uma $5$-coloração de $G$. Suponhamos, portanto, que $v$ tenha exatamente $5$ vizinhos, e que estes tenham cores distintas.

Seja $D$ um disco aberto em torno de $v$, tão pequeno que encontre apenas aqueles cinco segmentos de borda reta de $G$ que contém $v$. Vamos enumerar esses segmentos de acordo com sua posição cíclica em $D$ como $s_1, \dots, s_5$, e seja $vv_{i}$ a aresta que contém $s_{i} (i=1, \dots ,5)$. Sem perda de generalidade, podemos assumir que $\mathcal{c}(v_{i}) = i$ para cada $i$.

Vamos mostrar primeiro que todo $v_1-v_3$ caminho $P \subseteq H-\{v_2,v_4\}$ separa $v_2$ de $v_4$ em $H$. Claramente, este é o caso se, e somente se, o ciclo $C := vv_{1}Pv_{3}v$ separa $v_2$ de $v_4$ em $G$. Provamos isso mostrando que $v_2$ e $v_4$ estão em faces diferentes de $C$.

Vamos pegar um ponto interno $x_2$ de $s_2$ em $D$ e um ponto interno $x_4$ de $s_4$ em $D$. Então, em $D \setminus (s_1 \cup s_3) \subseteq \mathbb{R}^2 \setminus C$ todo ponto pode ser ligado por um arco poligonal a $x_2$ ou a $x_4$. Isso implica que $x_24 e $x_4$ (e, portanto, também $v_2$ e $v_4$) estão em diferentes faces de $C$: caso contrário, $D$ encontraria apenas uma das duas faces de $C$, o que contradiria o fato de que $v$ está na fronteira de ambas as faces (Teorema 4.1.1).

Dado $i,j \in \{1, \dots ,5\}$, seja $H_{i,j}$ o subgrafo de $H$ induzido pelos vértices coloridos $i$ ou $j$. Podemos assumir que a componente $C_1$ de $H_{1,3}$ contendo $v_1$ também contém $v_3$. De fato, se trocarmos as cores $1$ e $3$ em todos os vértices de $C_1$ , obtemos outra $5$-coloração de $H$; se $v_3 \notin C_1$ , então $v_1$ e $v_3$ são ambos coloridos $3$ nesta nova coloração, e podemos atribuir a cor $1$ a $v$. Assim, $H_{1,3}$ contém um $v_1-v_3$ caminho $P$. Como mostrado acima, $P$ separa $v_2$ de $v_44 em $H$. Como $P \cap H_{2,4} = \emptyset$, isso significa que $v_2$ e $v_4$ estão em componentes diferentes de $H_{2,4}$. No componente que contém $v_2$, agora trocamos as cores $2$ e $4$, recolorindo assim $v_2$ com a cor $4$. Agora $v$ não tem mais um vizinho colorido $2$, e podemos dar a ele esta cor.

Como pano de fundo para os dois famosos teoremas acima, vamos citar outro resultado bem conhecido: