Grafo cociente

En teoría de gráficas, una gráfica cociente es una gráfica construida a partir de un homomorfismo de gráficas mediante la siguiente construcción.

• Si $f:G\to H$ es un epimorfismo de gráficas y $V(H)=\{v1,v_{2},\ldots ,v_{m}\}$ es el conjunto de vértices de H, se pueden construir los conjuntos $S_{i}=f^{-1}(v_{i})$.
• La gráfica cociente $G/f$ es la gráfica cuyo conjunto de vértices está dado por $\{S_{1},S_{2},\ldots ,S_{m}\}$ y donde $S_{i}S_{j}$ es una arista de $G/f$ si y sólo si $v_{i}v_{j}$ es una arista de $H$.

Propiedades

• La gráfica cociente inducida por $f$ es una gráfica isomorfa a $H$.
• Cualquier $k-$coloración de $G$ corresponde a un epimorfismo de $G$ en la gráfica completa $K_{k}$.