Homomorfismos en gráficas, libro

Question

¿Me pueden recomendar un libro donde se hable sobre homomorfismos en gráficas, se den ejemplos, y si es posible, se hable un poco del aspecto algoritmico? Por ejemplo, que el problema es NP-completo, o si existen familias de gráficas para las que no lo es, etc.

O algún artículo muy básico que hable sobre homomorfismos.

Answer 1

No conozco ningún libro que tenga el aspecto algorítmico de homorfismos de gráficas. Acerca de homomorfismos (y en particular isomorfismos y automorfismos) de gráficas puedes encontrar mucha teoría y ejemplos en

Chris Godsil, Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001.

Por cierto, ¿a qué problema NP-completo te refieres?

Comments

Me refiero al problema de decidir, dadas dos gráficas, si existe un homomorfismo entre estas. También, me interesa saber si existen familias de gráficas para las que este problema sea polinomial.

Mirare el libro, gracias Daniel.

Answer 2

Encontre dos articulos introductorios pero bastantes completos, uno de los cuales cubre precisamente la parte computacional que estaba buscando. Dejo las referencias por si le fueran utiles a alguien.

Graph homomorphisms: structure and symmetry.
G Hahn, C Tardif- Graph Symmetry, 1997, Springer.
http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf

Gena Hahn and Gary MacGillivray. "Graph homomorphisms: computational aspects and infinite graphs". Research report, UniversitÈ de Montreal, June 2002.
http://www.ibrarian.net/navon/page.jsp?paperid=2984458&searchTerm=pilps+phase+2