Coloração de Grafos

Uma coloração própria de um grafo simples G=(V,E) é uma função que atribui uma cor a cada vértice, ou a cada aresta, de modo que elementos adjacentes recebam cores distintas. Em V a adjacência é a aresta {u,v}; em E, o extremo compartilhado.

χ, Brooks, χ′ e Vizing deste tópico reutilizam o mesmo G — sem laços nem arestas múltiplas — e o mesmo grau máximo Δ.

As páginas se agrupam em dois blocos. O primeiro pinta vértices: cada classe de cor é um conjunto independente, e χ(G) é o menor número de independentes que particionam V.

O segundo pinta arestas: cada classe de cor é um emparelhamento, e χ′(G) é o menor número de emparelhamentos cuja união cobre E.

Pintar V e obter χ está em Coloração de Vértices. Pintar E e obter o índice cromático χ′ está em Coloração de Arestas.

O piso ω da maior clique e o teto guloso Δ+1 estão em Coloração de Vértices. O piso Δ do feixe de arestas incidentes e o teto Δ+1 de Vizing estão em Coloração de Arestas.

Brooks, χ≤Δ fora de Kₙ e do ciclo ímpar, e as contas χ(C₅)=3=Δ+1 e χ(Kₙ)=n, estão em Coloração de Vértices. Classe 1 (χ′=Δ) ou classe 2 (χ′=Δ+1), com K₃ na classe 2, está em Coloração de Arestas.

χ=2 no bipartido está em Coloração de Vértices. König, χ′=Δ no mesmo bipartido, está em Coloração de Arestas.