Coloração de Grafos — Número Cromático e Aplicações

Coloração de grafos normalmente significa coloração de vértices: atribuir uma cor a cada vértice de modo que vértices adjacentes não compartilhem a mesma cor. O menor número de cores que funciona é o número cromático, escrito $\chi(G)$.

Se você quer a intuição rápida, as cores são apenas rótulos sem conflito. Dois vértices podem reutilizar a mesma cor exatamente quando não existe aresta entre eles.

Definição de coloração de grafos em um minuto

Em uma coloração própria, toda aresta conecta dois vértices com cores diferentes. Essa é a regra inteira.

Então, se $\chi(G)=3$, dois fatos são verdadeiros ao mesmo tempo:

• existe uma coloração própria com $3$ cores
• não existe uma coloração própria com apenas $2$ cores

É por isso que o número cromático é um mínimo, e não apenas o número de cores que você usou em um desenho específico.

A menos que alguém diga o contrário, coloração de grafos em um curso introdutório significa colorir os vértices de um grafo simples não direcionado. Coloração de arestas é um problema diferente, com regras diferentes.

O que o número cromático realmente mede

Os nomes das cores não importam. Você pode usar vermelho, azul e verde, ou os rótulos $1$, $2$ e $3$.

O que importa é o agrupamento. Todos os vértices com a mesma cor formam um conjunto sem arestas internas, então esse grupo não tem conflitos.

Essa perspectiva é o que torna a coloração de grafos útil em problemas de escalonamento e alocação. Uma cor muitas vezes significa “estes itens podem compartilhar o mesmo horário”.

Exemplo resolvido: por que um ciclo de 5 vértices precisa de 3 cores

Considere o grafo ciclo $C_5$ com arestas $AB, BC, CD, DE,$ e $EA$.

Tente primeiro com $2$ cores. Dê ao vértice $A$ a cor $1$ e ao vértice $B$ a cor $2$. Então a coloração fica forçada ao longo do ciclo:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Agora observe $E$. Ele é adjacente a $D$ e a $A$, então não pode usar a cor $2$ por causa de $D$, e não pode usar a cor $1$ por causa de $A$.

Portanto, $2$ cores falham.

Mas $3$ cores funcionam. Uma coloração própria é

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

logo

$$\chi(C_5)=3$$

Vale a pena lembrar deste exemplo porque ele mostra um padrão importante: para grafos ciclo, um ciclo par pode ser colorido com $2$ cores, mas um ciclo ímpar precisa de $3$.

Como raciocinar sobre coloração de grafos em grafos pequenos

Duas verificações rápidas ajudam.

Primeiro, procure um conflito forçado. No exemplo acima, alternar duas cores ao longo de um ciclo ímpar faz o último vértice entrar em conflito com as duas opções disponíveis.

Segundo, procure uma cota inferior. Se um grafo contém um triângulo, então esses três vértices são adjacentes dois a dois, então eles já precisam de $3$ cores diferentes. Isso nem sempre dá a resposta exata, mas prova que o número cromático é pelo menos $3$.

Erros comuns em problemas de coloração de grafos

Um erro comum é tratar vértices como adjacentes só porque foram desenhados próximos um do outro. Apenas uma aresta real cria uma restrição de coloração.

Outro erro é supor que todo vértice precisa de sua própria cor. Vértices não adjacentes podem reutilizar uma cor, e colorações eficientes normalmente reutilizam cores o máximo possível.

Os estudantes também às vezes confundem coloração de vértices com coloração de arestas. Nesta página, a regra é sobre vértices adjacentes, não arestas adjacentes.

Um erro final é informar o número de cores que você acabou usando em vez do número mínimo necessário. Usar $4$ cores em um grafo não prova que o número cromático é $4$.

Onde a coloração de grafos é usada

Uma aplicação padrão é em escalonamento. Suponha que cada vértice seja uma prova, e uma aresta signifique que duas provas têm alunos em comum e não podem ser marcadas no mesmo horário. Então uma cor pode representar um horário.

Nesse modelo, o número cromático informa o menor número possível de horários. Se $\chi(G)=4$, então não existe um cronograma válido com apenas $3$ horários.

A mesma ideia aparece na coloração de mapas, em que regiões vizinhas devem ser diferentes, e em projeto de compiladores, em que variáveis necessárias ao mesmo tempo não podem compartilhar o mesmo registrador.

Tente um problema parecido de coloração de grafos

Desenhe um grafo com vértices $P,Q,R,S,T$ e arestas $PQ, QR, RS, ST, TP,$ e $PR$.

Comece encontrando um triângulo para obter uma cota inferior. Depois tente colorir o grafo com o menor número possível de cores e verifique se algum par de vértices adjacentes ficou com a mesma cor. Se quiser um próximo passo, tente criar sua própria versão em um grafo maior e veja se você consegue provar que sua coloração é mínima, e não apenas válida.