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 es un epimorfismo de gráficas y es el conjunto de vértices de H, se pueden construir los conjuntos .
- La gráfica cociente es la gráfica cuyo conjunto de vértices está dado por y donde es una arista de si y sólo si es una arista de .
Propiedades
- La gráfica cociente inducida por es una gráfica isomorfa a .
- Cualquier coloración de corresponde a un epimorfismo de en la gráfica completa .
Bibliografía
- R. Balakrishnan; K. Ranganathan (1999). A Textbook of Graph Theory (en inglés). Board. ISBN 0387988599.