Colorações

Seja ${\cal{G}}=({\cal{V}}_{\cal{G}},{\cal{A}}_{\cal{G}})$ um grafo. Uma coloração de ${\cal{G}}$ é uma aplicação $f:{\cal{V}}_{\cal{G}}\rightarrow C$ tal que $f(v)\ne f(w)$ se $v\leftrightarrow w$, onde $C$ é um conjunto cujos elementos se chamam cores. Uma $k-$coloração é uma coloração $f$ tal que $\char93 f({\cal{V}}_{\cal{G}})=k$. O número cromático de ${\cal{G}}$, denotado por $\chi({\cal{G}})$, é o menor $k$ tal que existe uma $k-$coloração de ${\cal{G}}$. Por outras palavras, o número cromático de um grafo é o menor número de cores necessárias de forma a que dois vértices vizinhos tenham cores distintas. Por exemplo, um grafo bipartido com pelo menos uma aresta tem número cromático 2. Já o grafo completo $K_n$ tem número cromático $n$.

Teorema 8.1 (Teorema das 5 cores, P.J.Heawood, 1890)   Seja ${\cal{G}}$ um grafo simples planar. Então $\chi({\cal{G}})\le 5$.

Conjectura 8.2 (Conjectura das 4 cores, F.Guthrie, 1852)   O número cromático de qualquer grafo planar é não superior a 4.