19 Coloración

• Coloración de vértices
• Coloración de aristas
• Coloración de grafos planos

Teorema:

$G$ planar $\qquad\Longrightarrow\qquad$ los vértices de $G$ son colorables con 4 colores

$G$ planar que no contiene ningún triángulo $\qquad\Longrightarrow\qquad$ los vértices de $G$ son colorables con 3 colores

Notaciones:

$\chi(G)$	número mínimo de colores que se necesita para
	colorar los vértices de un grafo
$\chi^\prime(G)$	número mínimo de colores que se necesita para
	colorar las aristas de un grafo

Teorema (Brooks):

$G$ conexo $G\neq C^{\mbox{impar}}$ y $G\neq K^n$ $\qquad\Longrightarrow\qquad$ $\chi(G)\leq \Delta(G)$

Teorema (Koenig):

$G$ bipartido $\qquad\Longrightarrow\qquad$ $\chi^\prime(G)=\Delta(G)$