Grafo cociente

En teoría de gráficas, un grafo cociente o 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,\dots ,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,\dots ,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$.

Bibliografía

• Plantilla:Cita libro