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

Propiedades

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

Bibliografía

• R. Balakrishnan; K. Ranganathan (1999). A Textbook of Graph Theory (en inglés). Board. ISBN 0387988599. 

•   Datos: Q5884097