Coloração de Grafos

A coloração de grafos atribui rótulos, ou cores, aos elementos de um grafo de modo que elementos adjacentes difiram, e estuda o número mínimo de cores necessárias.

Definition

Uma coloração própria de um grafo é uma atribuição de cores aos seus vértices de modo que dois vértices adjacentes não compartilhem a mesma cor; o número cromático é o menor número de cores para o qual tal atribuição existe.

Scope

Este tópico aborda a coloração própria de vértices e o número cromático, a coloração de arestas e o índice cromático, o polinômio cromático que contabiliza as colorações, e resultados marcantes, incluindo o teorema de Brooks, o teorema de Vizing e o Teorema das Quatro Cores para grafos planares. Ele relaciona a coloração com a independência, cliques e a teoria mais ampla dos parâmetros de grafos.

Core questions

• Qual é o menor número de cores necessárias para colorir adequadamente um dado grafo?
• Quantas colorações próprias com uma dada paleta um grafo admite?
• Quais grafos podem ser coloridos com poucas cores e quais obstruções exigem muitas?
• Como as colorações de arestas e as colorações de lista estendem a noção básica?

Key concepts

• Coloração própria de vértices
• Número cromático
• Polinômio cromático
• Coloração de arestas e índice cromático
• Teorema de Brooks
• Teorema das Quatro Cores

Key theories

Teorema das Quatro Cores

Todo grafo planar pode ser propriamente colorido com no máximo quatro cores, uma afirmação que permaneceu em aberto por mais de um século e foi provada pela primeira vez por Appel e Haken em 1976 usando uma extensa análise de casos assistida por computador.

Teorema de Vizing

As arestas de qualquer grafo simples podem ser propriamente coloridas com o grau máximo ou com uma cor a mais do que o grau máximo, dividindo todos os grafos em duas classes restritas.

Clinical relevance

A coloração modela a alocação de recursos sem conflitos: o agendamento sem colisões, a alocação de registradores em compiladores, a atribuição de frequências em redes sem fio e problemas de restrição no estilo Sudoku podem ser reduzidos à coloração de grafos.

History

A Conjectura das Quatro Cores, proposta em 1852, impulsionou grande parte da teoria da coloração; sua prova assistida por computador em 1976 por Appel e Haken foi um marco inicial na matemática assistida por computador e gerou debate sobre a natureza da prova.

Debates

Status das provas assistidas por computador

A dependência do Teorema das Quatro Cores em casos verificados por máquina levantou a questão se uma prova muito longa para ser verificada manualmente por um humano deveria ser considerada uma prova matemática genuína.

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

O que é o número cromático de um grafo?

É o menor número de cores necessárias para que vértices adjacentes sempre recebam cores diferentes; por exemplo, um ciclo ímpar tem número cromático três.

O Teorema das Quatro Cores se aplica a todos os mapas?

Ele se aplica a mapas desenhados no plano ou esfera onde as regiões são conectadas; mapas em superfícies como o toro podem exigir mais cores.